Hardness of equivalence checking for composed finite-state systems

1. Balcázar J., Gabarró J., Sántha M.: Deciding bisimilarity is P-complete. Formal Aspects Comput. 4(6A), 638–648 (1992)

   Article  MATH  Google Scholar 

2. Chandra A.K., Kozen D.C., Stockmeyer L.J.: Alternation. J. ACM. 28(1), 114–133 (1981)

   Article  MATH  MathSciNet  Google Scholar 

3. van Glabbeek R.: Handbook of process algebra. In: Bergstra, J., Ponse, A., Smolka, S. (eds.) Handbook of Process Algebra, chap. The Linear Time—Branching Time Spectrum, pp. 3–99. Elsevier, Amsterdam (2001)

   Google Scholar 

4. Groote, J.F., Moller, F.: Verification of parallel systems via decomposition. In: Proceedings of Third International Conference on Concurrency Theory. Lecture Notes in Computer Science, vol. 630, pp. 62–76. Springer, Heidelberg (1992)

5. Hoare C.A.R.: Communcating Sequential Processes. Prentice-Hall, Englewood Cliffs (1985)

   Google Scholar 

6. Immerman, N.: Descriptive Complexity, pp. 53–54. Springer, Heidelberg (1998)

   Google Scholar 

7. Jančar, P., Srba, J.: Undecidability of bisimilarity by Defender’s forcing. J. ACM. 55(1) (2008)

8. Kanellakis P.C., Smolka S.A.: CCS expressions, finite state processes, and three problems of equivalence. Inf. Comput. 86(1), 43–68 (1990)

   Article  MATH  MathSciNet  Google Scholar 

9. Laroussinie, F., Schnoebelen, P.: The state explosion problem from trace to bisimulation equivalence. In: Proceedings of the 3rd International Conference Foundations of Software Science and Computation Structures (FOSSACS’2000), Berlin, Germany, March–April 2000. Lecture Notes in Computer Science, vol. 1784, pp. 192–207. Springer, Heidelberg (2000)

10. Mansfield, A.: On the computational complexity of a merge recognition problem. DAMATH: Discrete Appl. Math. Combin. Oper. Res. Comput. Sci. 5, 119–122 (1983)

    MATH  MathSciNet  Google Scholar 

11. Meyer, A.R., Stockmeyer, L.J.: The equivalence problem for regular expressions with squaring requires exponential space. In: 13th Annual Symposium on Switching and Automata Theory, pp. 125–129. IEEE, New York (1972)

12. Milner R.: Communication and Concurrency. Prentice-Hall, Englewood Cliffs (1989)

    MATH  Google Scholar 

13. Paige R., Tarjan R.E.: Three partition refinement algorithms. SIAM J. Comput. 16(6), 973–989 (1987)

    Article  MATH  MathSciNet  Google Scholar 

14. Rabinovich A.: Complexity of equivalence problems for concurrent systems of finite agents. Inf. Comput. 139(2), 111–129 (1997)

    Article  MATH  MathSciNet  Google Scholar 

15. Sawa, Z.: Equivalence checking of non-flat systems is EXPTIME-hard. In: Proceedings of CONCUR 2003. Lecture Notes in Computer Science, vol. 2761, pp. 237–250. Springer, Heidelberg (2003)

16. Sawa Z., Jančar P.: Behavioural equivalences on finite-state systems are PTIME-hard. Comput. Inform. 24(5), 513–528 (2005)

    MATH  MathSciNet  Google Scholar 

17. Shukla, S.K., Hunt, H.B., Rosenkrantz, D.J., Stearns, R.E.: On the complexity of relational problems for finite state processes. In: Proceedings of ICALP’96. Lecture Notes in Computer Science, vol. 1099, pp. 466–477. Springer, Heidelberg (1996)

18. Valmari, A., Kervinen, A.: Alphabet-based synchronisation is exponentially cheaper. In: Proceedings of CONCUR 2002. Lecture Notes in Computer Science, vol. 2421, pp. 161–176 (2002)

19. Warmuth M.K., Haussler D.: On the complexity of iterated shuffle. J. Comp. Syst. Sci. 28(3), 345–358 (1984)

    Article  MATH  MathSciNet  Google Scholar 

Download references