A classification of symbolic transition systems

T.A. Henzinger, R. Majumdar, J. Raskin, ACM Transactions on Computational Logic (TOCL) 6 (2005) 1–32.

Download
No fulltext has been uploaded. References only!

Journal Article | Published
Author
; ;
Abstract
We define five increasingly comprehensive classes of infinite-state systems, called STS1--STS5, whose state spaces have finitary structure. For four of these classes, we provide examples from hybrid systems.STS1 These are the systems with finite bisimilarity quotients. They can be analyzed symbolically by iteratively applying predecessor and Boolean operations on state sets, starting from a finite number of observable state sets. Any such iteration is guaranteed to terminate in that only a finite number of state sets can be generated. This enables model checking of the μ-calculus.STS2 These are the systems with finite similarity quotients. They can be analyzed symbolically by iterating the predecessor and positive Boolean operations. This enables model checking of the existential and universal fragments of the μ-calculus.STS3 These are the systems with finite trace-equivalence quotients. They can be analyzed symbolically by iterating the predecessor operation and a restricted form of positive Boolean operations (intersection is restricted to intersection with observables). This enables model checking of all ω-regular properties, including linear temporal logic.STS4 These are the systems with finite distance-equivalence quotients (two states are equivalent if for every distance d, the same observables can be reached in d transitions). The systems in this class can be analyzed symbolically by iterating the predecessor operation and terminating when no new state sets are generated. This enables model checking of the existential conjunction-free and universal disjunction-free fragments of the μ-calculus.STS5 These are the systems with finite bounded-reachability quotients (two states are equivalent if for every distance d, the same observables can be reached in d or fewer transitions). The systems in this class can be analyzed symbolically by iterating the predecessor operation and terminating when no new states are encountered (this is a weaker termination condition than above). This enables model checking of reachability properties.
Publishing Year
Date Published
2005-01-01
Journal Title
ACM Transactions on Computational Logic (TOCL)
Volume
6
Issue
1
Page
1 - 32
IST-REx-ID

Cite this

Henzinger TA, Majumdar R, Raskin J. A classification of symbolic transition systems. ACM Transactions on Computational Logic (TOCL). 2005;6(1):1-32. doi:10.1145/1042038.1042039
Henzinger, T. A., Majumdar, R., & Raskin, J. (2005). A classification of symbolic transition systems. ACM Transactions on Computational Logic (TOCL), 6(1), 1–32. https://doi.org/10.1145/1042038.1042039
Henzinger, Thomas A, Ritankar Majumdar, and Jean Raskin. “A Classification of Symbolic Transition Systems.” ACM Transactions on Computational Logic (TOCL) 6, no. 1 (2005): 1–32. https://doi.org/10.1145/1042038.1042039.
T. A. Henzinger, R. Majumdar, and J. Raskin, “A classification of symbolic transition systems,” ACM Transactions on Computational Logic (TOCL), vol. 6, no. 1, pp. 1–32, 2005.
Henzinger TA, Majumdar R, Raskin J. 2005. A classification of symbolic transition systems. ACM Transactions on Computational Logic (TOCL). 6(1), 1–32.
Henzinger, Thomas A., et al. “A Classification of Symbolic Transition Systems.” ACM Transactions on Computational Logic (TOCL), vol. 6, no. 1, ACM, 2005, pp. 1–32, doi:10.1145/1042038.1042039.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar