Deciding bisimilarity of normed context-free processes is in \(\Sigma_ 2^ p\). (English) Zbl 0801.68058

Summary: Existing decision algorithms for bisimulation equivalence for normed context-free processes require at least exponential time. We develop a \(\sum^ p_ 2\) (a subclass of PSPACE) algorithm for deciding bisimulation equivalence for normed context-free processes.


68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68Q55 Semantics in the theory of computing
Full Text: DOI


[1] Alvarez, C.; Balcázar, J.L.; Gabarró, J.; Santha, M., Parallel complexity in the design and analysis of concurrent systems, ()
[2] Baeten, J.C.M.; Bergstra, J.A.; Klop, J.W., Decidability of bisimulation equivalence for processes generating context-free languages, () · Zbl 0635.68014
[3] Bergstra, J.A.; Klop, J.W., Process theory based on bisimulation semantics, (), 50-122 · Zbl 0683.68066
[4] Caucal, D., A fast algorithm to decide on simple grammars equivalence, (), 66-85 · Zbl 0704.68072
[5] Caucal, D., Graphes canoniques de graphes algèbriques, Theoret. inform. appl., 24, 339-352, (1990) · Zbl 0701.68082
[6] Garey, M.R.; Johnson, D.S., Computers and intractability: A guide to the theory of NP-completeness, (1979), Freeman New York · Zbl 0411.68039
[7] van Glabbeek, R.J., The linear time — branching time spectrum, (), 278-297
[8] Groote, J.F., A short proof of the decidability of bisimulation for normed BPA-processes, Tech. report CS-R9151, (1991), CWI
[9] Groote, J.F.; Hüttel, H., Undecidable equivalences for basic process algebra, Tech. report CS-R9137, (1991), CWI
[10] Harrison, M.A., Introduction to formal language theory, (1978), Addison-Wesley Reading, MA · Zbl 0411.68058
[11] Hopcroft, J.E.; Ullman, J.D., Introduction to automata theory, languages and computation, (1979), Addison-Wesley Reading, MA · Zbl 0196.01701
[12] Hüttel, H.; Stirling, C., Actions speak louder than words: proving bisimilarity for context-free processes, Proc. 6th annual symp. on logic in computer science, 376-386, (1991)
[13] Huynh, D.T.; Tian, L., Complexity of deciding readiness and failure equivalences for processes, Proc. 3rd IEEE symp. on parallel and distributed processing, 738-745, (1991)
[14] Huynh, D.T.; Tian, L., A note on the complexity of deciding bisimilarity of normed unary processes, () · Zbl 0809.68066
[15] Kanellakis, P.C.; Smolka, S.A., CCS expressions, finite state processes and three problems of equivalence, Inform. and comput., 86, 43-68, (1990) · Zbl 0705.68063
[16] Milner, R., Communication and concurrency, (1989), Prentice-Hall Englewood Cliffs, NJ · Zbl 0683.68008
[17] Park, D., Concurrency and automata on infinite sequences, (), 168-183
[18] Stockmeyer, L.J., The polynomial time hierarchy, Theoret. comput. sci., 3, 1-22, (1977) · Zbl 0353.02024
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.