Complexity of compositional model checking of computation tree logic on simple structures

K. Chatterjee, P. Dasgupta, P. Chakrabarti, in:, Springer, 2005, pp. 89–102.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published
Author
; ;
Series Title
LNCS
Abstract
Temporal Logic Model Checking is one of the most potent tools for the verification of finite state systems. Computation Tree Logic (CTL) has gained popularity because unlike most other logics, CTL model checking of a single transition system can be achieved in polynomial time. However, in most real-life problems, specially in distributed and parallel systems, the system consist of a set of concurrent processes and the verification problem translates to model check the composition of the component processes. Since explicit composition leads to state explosion, verifying the system without actually composing the components is attractive, even for possibly restrictive class of systems. We show that the problem of compositional CTL model checking is PSPACE complete for the class of systems composed of components that are tree-like transition structure and do not interact among themselves. For the simplest forms of existential and universal CTL formulas model checking turns out to be NP complete and coNP complete, respectively. The results hold for both synchronous and asynchronous composition.
Publishing Year
Date Published
2005-02-14
Acknowledgement
Pallab Dasgupta and P.P.Chakrabarti thank the Dept. of Science & Tech., Govt. of India, for partial support of this work
Volume
3326
Page
89 - 102
Conference
IWDC: International Workshop on Distributed Computing
IST-REx-ID

Cite this

Chatterjee K, Dasgupta P, Chakrabarti P. Complexity of compositional model checking of computation tree logic on simple structures. In: Vol 3326. Springer; 2005:89-102. doi:10.1007/978-3-540-30536-1_13
Chatterjee, K., Dasgupta, P., & Chakrabarti, P. (2005). Complexity of compositional model checking of computation tree logic on simple structures (Vol. 3326, pp. 89–102). Presented at the IWDC: International Workshop on Distributed Computing , Springer. https://doi.org/10.1007/978-3-540-30536-1_13
Chatterjee, Krishnendu, Pallab Dasgupta, and Partha Chakrabarti. “Complexity of Compositional Model Checking of Computation Tree Logic on Simple Structures,” 3326:89–102. Springer, 2005. https://doi.org/10.1007/978-3-540-30536-1_13.
K. Chatterjee, P. Dasgupta, and P. Chakrabarti, “Complexity of compositional model checking of computation tree logic on simple structures,” presented at the IWDC: International Workshop on Distributed Computing , 2005, vol. 3326, pp. 89–102.
Chatterjee K, Dasgupta P, Chakrabarti P. 2005. Complexity of compositional model checking of computation tree logic on simple structures. IWDC: International Workshop on Distributed Computing , LNCS, vol. 3326. 89–102.
Chatterjee, Krishnendu, et al. Complexity of Compositional Model Checking of Computation Tree Logic on Simple Structures. Vol. 3326, Springer, 2005, pp. 89–102, doi:10.1007/978-3-540-30536-1_13.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar