Fast Algorithms for Handling Diagonal Constraints in Timed Automata
Publication
, Conference
Gastin, P; Mukherjee, S; Srivathsan, B
Published in: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
January 1, 2019
A popular method for solving reachability in timed automata proceeds by enumerating reachable sets of valuations represented as zones. A naïve enumeration of zones does not terminate. Various termination mechanisms have been studied over the years. Coming up with efficient termination mechanisms has been remarkably more challenging when the automaton has diagonal constraints in guards. In this paper, we propose a new termination mechanism for timed automata with diagonal constraints based on a new simulation relation between zones. Experiments with an implementation of this simulation show significant gains over existing methods.
Duke Scholars
Published In
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
DOI
EISSN
1611-3349
ISSN
0302-9743
ISBN
9783030255398
Publication Date
January 1, 2019
Volume
11561 LNCS
Start / End Page
41 / 59
Related Subject Headings
- Artificial Intelligence & Image Processing
- 46 Information and computing sciences
Citation
APA
Chicago
ICMJE
MLA
NLM
Gastin, P., Mukherjee, S., & Srivathsan, B. (2019). Fast Algorithms for Handling Diagonal Constraints in Timed Automata. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (Vol. 11561 LNCS, pp. 41–59). https://doi.org/10.1007/978-3-030-25540-4_3
Gastin, P., S. Mukherjee, and B. Srivathsan. “Fast Algorithms for Handling Diagonal Constraints in Timed Automata.” In Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 11561 LNCS:41–59, 2019. https://doi.org/10.1007/978-3-030-25540-4_3.
Gastin P, Mukherjee S, Srivathsan B. Fast Algorithms for Handling Diagonal Constraints in Timed Automata. In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2019. p. 41–59.
Gastin, P., et al. “Fast Algorithms for Handling Diagonal Constraints in Timed Automata.” Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11561 LNCS, 2019, pp. 41–59. Scopus, doi:10.1007/978-3-030-25540-4_3.
Gastin P, Mukherjee S, Srivathsan B. Fast Algorithms for Handling Diagonal Constraints in Timed Automata. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2019. p. 41–59.
Published In
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
DOI
EISSN
1611-3349
ISSN
0302-9743
ISBN
9783030255398
Publication Date
January 1, 2019
Volume
11561 LNCS
Start / End Page
41 / 59
Related Subject Headings
- Artificial Intelligence & Image Processing
- 46 Information and computing sciences