Symbolic model checking for rectangular hybrid systems
Henzinger TA, Majumdar R. 2000. Symbolic model checking for rectangular hybrid systems. Proceedings of the 6th International Conference on Tools and Algorithms for the Construction and Analysis of Systems. TACAS: Tools and Algorithms for the Construction and Analysis of Systems, LNCS, vol. 1785, 142–156.
Download
No fulltext has been uploaded. References only!
Conference Paper
| Published
| English
Scopus indexed
Author
Henzinger, Thomas AISTA 
;
Majumdar, Ritankar
;
Majumdar, RitankarSeries Title
LNCS
Abstract
An important case of hybrid systems are the rectangular automata. First, rectangular dynamics can naturally and arbitrarily closely approximate more general, nonlinear dynamics. Second, rectangular automata are the most general type of hybrid systems for which model checking -in particular, Ltl model checking- is decidable. However, on one hand, the original proofs of decidability did not suggest practical algorithms and, on the other hand, practical symbolic model-checking procedures -such as those implemented in HyTech- were not known to terminate on rectangular automata. We remedy this unsatisfactory situation: we present a symbolic method for Ltl model checking which can be performed by HyTech and is guaranteed to terminate on all rectangular automata. We do so by proving that our method for symbolic Ltl model checking terminates on an infinite-state transition system if the trace-equivalence relation of the system has finite index, which is the case for all rectangular automata.
Publishing Year
Date Published
2000-01-01
Proceedings Title
Proceedings of the 6th International Conference on Tools and Algorithms for the Construction and Analysis of Systems
Publisher
Springer
Acknowledgement
This research was supported in part by the DARPA (NASA) grant NAG2-1214, the DARPA (Wright-Patterson AFB) grant F33615-C-98-3614, the MARCO grant 98-DT-660, the ARO MURI grant DAAH-04-96-1-0341, and the NSF CAREER award CCR-9501708.
Volume
1785
Page
142 - 156
Conference
TACAS: Tools and Algorithms for the Construction and Analysis of Systems
Conference Location
Berlin, Germany
Conference Date
2000-03-25 – 2000-04-02
ISBN
IST-REx-ID
Cite this
Henzinger TA, Majumdar R. Symbolic model checking for rectangular hybrid systems. In: Proceedings of the 6th International Conference on Tools and Algorithms for the Construction and Analysis of Systems. Vol 1785. Springer; 2000:142-156. doi:10.1007/3-540-46419-0_11
Henzinger, T. A., & Majumdar, R. (2000). Symbolic model checking for rectangular hybrid systems. In Proceedings of the 6th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (Vol. 1785, pp. 142–156). Berlin, Germany: Springer. https://doi.org/10.1007/3-540-46419-0_11
Henzinger, Thomas A, and Ritankar Majumdar. “Symbolic Model Checking for Rectangular Hybrid Systems.” In Proceedings of the 6th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, 1785:142–56. Springer, 2000. https://doi.org/10.1007/3-540-46419-0_11.
T. A. Henzinger and R. Majumdar, “Symbolic model checking for rectangular hybrid systems,” in Proceedings of the 6th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, Berlin, Germany, 2000, vol. 1785, pp. 142–156.
Henzinger TA, Majumdar R. 2000. Symbolic model checking for rectangular hybrid systems. Proceedings of the 6th International Conference on Tools and Algorithms for the Construction and Analysis of Systems. TACAS: Tools and Algorithms for the Construction and Analysis of Systems, LNCS, vol. 1785, 142–156.
Henzinger, Thomas A., and Ritankar Majumdar. “Symbolic Model Checking for Rectangular Hybrid Systems.” Proceedings of the 6th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, vol. 1785, Springer, 2000, pp. 142–56, doi:10.1007/3-540-46419-0_11.
Google Scholar
ISBN Search