On the Computational Complexity of Bisimulation, Redux

Warning

This publication doesn't include Faculty of Education. It includes Faculty of Informatics. Official publication website can be found on muni.cz.

Authors	MOLLER Faron SMOLKA Scot SRBA Jiří
Year of publication	2004
Type	Article in Periodical
Magazine / Source	Information and Computation
MU Faculty or unit	Faculty of Informatics
Citation
Web	http://www.brics.dk/~srba/publ.html
Field	Informatics
Keywords	bisimilarity; complexity
Description	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 [Moller,Smolka'95]. 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.
Related projects:	Verification of infinite-state systems Non-sequential Models of Computing -- Quantum and Concurrent Distributed Models of Computing