Abstract
We present new complexity results for simulation-checking and modelchecking with infinite-state systems generated by pushdown automata and their proper subclasses of one-counter automata and one-counter nets (one-counter nets are ‘weak’ one-counter automata computationally equivalent to Petri nets with at most one unbounded place). As for simulation-checking, we show the following: a) simulation equivalence between pushdown processes and finite-state processes is EXPTIME-complete; b) simulation equivalence between processes of one-counter automata and finitestate processes is coNP-hard; c) simulation equivalence between processes of one-counter nets and finite-state processes is in P (to the best of our knowledge, it is the first (and rather tight) polynomiality result for simulation with infinitestate processes). As for model-checking, we prove that a) the problem of simulation-checking between processes of pushdown automata (or one-counter automata, or one-counter nets) and finite-state processes are polynomially reducible to the model-checking problem with a fixed formula ϕ ≡ νX.[z]〈z〉of the modal μ-calculus. Consequently, model-checking with ϕ. is EXPTIME-complete for pushdown processes and coNP-hard for processes of one-counter automata; b) model-checking with a fixed formula ◊[a]◊[b]ff of the logic EF (a simple fragment of CTL) is NP-hard for processes of OC nets, and model-checking with another fixed formula □〈〉□〈〉tt of EF is coNP-hard. Consequently, model-checking with any temporal logic which can express these simple formulae is computationally hard even for the (very simple) sequential processes of OC-nets.
Supported by the Grant Agency of the Czech Republic, grants No. 201/98/P046 and No. 201/00/1023.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
P. A. Abdulla and K. Čerāns. Simulation is decidable for one-counter nets. In Proceedings of CONCUR’98, volume 1466of Lecture Notes in Computer Science, pages 253–268. Springer, 1998.
H. R. Andersen. Verification of Temporal Properties of Concurrent Systems. PhD thesis, Arhus University, 1993.
E. Bach and J. Shallit. Algorithmic Number Theory. Vol. 1, Efficient Algorithms. The MIT Press, 1996.
J. C. M. Baeten and W. P. Weijland. Process Algebra. Number 18 in Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, 1990.
S. Christensen. Decidability and Decomposition in Process Algebras. PhD thesis, The University of Edinburgh, 1993.
E. A. Emerson. Temporal and modal logic. Handbook of Theoretical Computer Science, B, 1991.
J. Esparza and J. Knop. An automata-theoretic approach to interprocedural data-flow analysis. In Proceedings of FoSSaCS’99, volume 1578of Lecture Notes in Computer Science, pages 14–30. Springer, 1999.
J. F. Groote and H. Hüttel. Undecidable equivalences for basic process algebra. Information and Computation, 115(2):353–371, 1994.
Y. Hirshfeld. Petri nets and the equivalence problem. In Proceedings of CSL’93, volume 832 of Lecture Notes in Computer Science, pages 165–174. Springer, 1994.
P. Jančar, A. Kučera, and R. Mayr. Deciding bisimulation-like equivalences with finite-state processes. In Proceedings of ICALP’98, volume 1443of Lecture Notes in Computer Science, pages 200–211. Springer, 1998.
P. Jančar and F. Moller. Checking regular properties of Petri nets. In Proceedings of CONCUR’ 95, volume 962 of Lecture Notes in Computer Science, pages 348–362. Springer, 1995.
P. Jančar, F. Moller, and Z. Sawa. Simulation problems for one-counter machines. In Proceedings of SOFSEM’99, volume 1725 of Lecture Notes in Computer Science, pages 404–413. Springer, 1999.
D. Kozen. Results on the propositional u-calculus. Theoretical Computer Science, 27:333–354, 1983.
A. Kučera. Efficient verification algorithms for one-counter processes. In Proceedings of ICALP 2000, volume 1853 of Lecture Notes in Computer Science, pages 317–328. Springer, 2000.
A. Kučera. On simulation-checking with sequential systems. Technical report FIMU-RS-2000-05, Faculty of Informatics, Masaryk University, 2000.
A. Kučera and R. Mayr. Simulation preorder on simple process algebras. In Proceedings of ICALP’99, volume 1644of Lecture Notes in Computer Science, pages 503–512. Springer, 1999.
A. Kučera and R. Mayr. Weak bisimilarity with infinite-state systems can be decided in polynomial time. In Proceedings of CONCUR’99, volume 1664of Lecture Notes in Computer Science, pages 368–382. Springer, 1999.
F. Laroussinie and Ph. Schnoebelen. The state explosion problem from trace to bisimulation equivalence. In Proceedings of FoSSaCS 2000, volume 1784 of Lecture Notes in Computer Science, pages 192–207. Springer, 2000.
R. Mayr. On the complexity of bisimulation problems for pushdown automata. In Proceedings of IFIP TCS’2000, volume 1872of Lecture Notes in Computer Science. Springer, 2000.
R. Milner. Communication and Concurrency. Prentice-Hall, 1989.
D. M. R. Park. Concurrency and automata on infinite sequences. In Proceedings 5th GI Conference, volume 104 of Lecture Notes in Computer Science, pages 167–183. Springer, 1981.
W. Reisig. Petri Nets — An Introduction. Springer, 1985.
C. Stirling. Modal and temporal logics. Handbook of Logic in Computer Science, 2:477–563, 1992.
R. J. van Glabbeek. The linear time-branching time spectrum. In Proceedings of CONCUR’ 90, volume 458 of Lecture Notes in Computer Science, pages 278–297. Springer, 1990.
I. Walukiewicz. Pushdown processes: Games and model checking. In Proceedings of CAV’96, volume 1102 of Lecture Notes in Computer Science, pages 62–74. Springer, 1996.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kučera, A. (2000). On Simulation-Checking with Sequential Systems. In: Jifeng, H., Sato, M. (eds) Advances in Computing Science — ASIAN 2000. ASIAN 2000. Lecture Notes in Computer Science, vol 1961. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44464-5_11
Download citation
DOI: https://doi.org/10.1007/3-540-44464-5_11
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-41428-5
Online ISBN: 978-3-540-44464-0
eBook Packages: Springer Book Archive