Decidability of bisimulation equivalence for processes generating context-free languages. (English) Zbl 0635.68014

PARLE, Parallel architectures and languages Europe, Proc. Conf., Eindhoven/Neth. 1987, Vol. 2, Lect. Notes Comput. Sci. 259, 94-111 (1987).
[For the entire collection see Zbl 0608.00014.]
The authors show that the problem of equality of the processes generating context-free languages is decidable. The equality of processes is considered in the sense of equality obtained by dividing out the bisimulation equivalence in the domain of process graphs. The proof is given by displaying a periodic structure of the process graphs determined by context-free grammars in Greibach normal form.
Reviewer: N.Huhro


68N25 Theory of operating systems
68Q55 Semantics in the theory of computing
68Q45 Formal languages and automata


Zbl 0608.00014