A note on the complexity of deciding bisimilarity of normed unary processes. (English) Zbl 0809.68066

Summary: We give \(\text{NC}^ 1\) reduction of bisimulation equivalence for (general) normed context-free processes to the same problem for normed unary context-free processes.


68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI


[1] Alvarez, C.; Balcázar, J.L.; Gabarró, J.; Santha, M., Parallel complexity in the design and analysis of concurrent systems, (), 288-303
[2] Baeten, J.C.M.; Bergstra, J.A.; Klop, J.W., Decidability of bisimulation equivalence for processes generating context-free languages, J. ACM, 40, 3, 653-682, (1993) · Zbl 0801.68102
[3] Caucal, D., Graphes canoniques de graphes algébriques, Theoret. inform. appl., 24, 4, 339-352, (1990) · Zbl 0701.68082
[4] Christensen, S.; Hüttel, H., Decidability issues for infinite-state processes—A survey, EATCS bull., 51, 156-166, (1993) · Zbl 0783.68042
[5] Cook, S.A., A taxonomy of problems with fast parallel algorithms, Inform. and control, 64, 2-22, (1985) · Zbl 0575.68045
[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] Groote, J.F., A short proof of the decidability of bisimulation for normed BPA-processes, Inform. process. lett., 42, 167-171, (1992) · Zbl 0779.68029
[8] Groote, J.F.; Hüttel, H., Undecidable equivalences for basic process algebra, () · Zbl 0834.68069
[9] Hopcroft, J.E.; Ullman, J.D., Introduction to automata theory, languages and computation, (1979), Addison-Wesley Reading, MA · Zbl 0196.01701
[10] Huynh, D.T., Deciding the inequivalence of context-free grammars with 1-letter terminal alphabet is σ^{p}2-complete, Theoret. comput. sci., 33, 305-326, (1984) · Zbl 0556.68040
[11] 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)
[12] 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), to appear in Inform. and Comput.
[13] Huynh, D.T.; Tian, L., Deciding bisimilarity of normed context-free processes is in σ^{p}2, Theoret. comput. sci., 123, 183-197, (1994) · Zbl 0801.68058
[14] 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
[15] Milner, R., Communication and concurrency, (1989), Prentice-Hall Englewood Cliffs, NJ · Zbl 0683.68008
[16] Park, D., Concurrency and automata on infinite sequences, (), 168-183
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.