Actions speak louder than words: proving bisimilarity for context-free processes
- 10 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 8 (4) , 376-386
- https://doi.org/10.1109/lics.1991.151661
Abstract
J.C.M. Baeten et al. (Lecture Notes in Computer Science, vol. 259, pp. 93-114, 1987) proved that bisimulation equivalence is decidable for irredundant context-free grammars. A much simpler and much more direct proof of this result is provided now. It uses a tableau decision method involving goal-directed rules. The decision procedure yields an upper bound on a tableau depth. Moreover, it provides the essential part of the bisimulation relation between two processes which underlies their equivalence. A second virtue is that it provides a sound and complete equational theory for such processes.Keywords
This publication has 4 references indexed in Scilit:
- Algebraic laws for nondeterminism and concurrencyJournal of the ACM, 1985
- A complete inference system for a class of regular behavioursJournal of Computer and System Sciences, 1984
- Process algebra for synchronous communicationInformation and Control, 1984
- Simple deterministic languagesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1966