On the computational complexity of bisimulation, redux |
| |
| Authors: | Faron Moller, Scott Smolka,Ji&#x í Srba |
| |
| Affiliation: | a Department of Computer Science, University of Wales Swansea, Singleton Park, Swansea SA2 8PP, Wales, UK;b Department of Computer Science, SUNY at Stony Brook, Stony Brook, NY 11790-4400, USA;c BRICS, Aalborg University, Fr. Bajersvej 7B, 9220 Aalborg, Denmark |
| |
| Abstract: | Paris Kanellakis and the second author (Smolka) were among the first to investigate the computational complexity of bisimulation, and the first and third authors (Moller and Srba) have long-established track records in the field. Smolka and Moller have also written a brief survey about the computational complexity of bisimulation [ACM Comput. Surv. 27(2) (1995) 287]. The authors believe that the special issue of Information and Computation devoted to PCK50: Principles of Computing and Knowledge: Paris C. Kanellakis Memorial Workshop represents an ideal opportunity for an up-to-date look at the subject. |
| |
| Keywords: | One-counter machines Equivalence-checking Model-checking Automata Formal languages Bisimulation equivalence Complexity |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
