Abstract
A context-free grammar (CFG) in Greibach Normal Form coincides, in another notation, with a system of guarded recursion equations in Basic Process Algebra. Hence to each CFG a process can be assigned as solution, which has as its set of finite traces the context-free language (CFL) determined by that CFG. While the equality problem for CFL's is unsolvable, the equality problem for the processes determined by CFG's turns out to be solvable. Here equality on processes is given by a model of process graphs modulo bisimulation equivalence. The proof is given by displaying a periodic structure of the process graphs determined by CFG's. As a corollary of the periodicity a short proof of the solvability of the equivalence problem for simple context-free languages is given.
Authors partially supported by ESPRIT project 432, Meteor.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
J.C.M. Baeten, J.A. Bergstra, Global renaming operators in concrete process algebra, Report CS-R8521, Centre for Mathematics and Computer Science, Amsterdam 1985.
J.C.M. Baeten, J.A. Bergstra, J.W. Klop, On the consistency of Koomen's Fair Abstraction Rule, Report CS-R8511, Centre for Mathematics and Computer Science, Amsterdam 1985. To appear in Theoret. Comput. Sci.
J.C.M. Baeten, J.A. Bergstra, J.W. Klop, Decidability of bisimulation equivalence for processes generating context-free languages, Report CS-R8632, Centre for Mathematics and Computer Science, Amsterdam 1986.
J.W. de Bakker, J.A. Bergstra, J.W. Klop, J.-J.Ch. Meyer, Linear time and branching time semantics for recursion with merge, in: Proc. 10th ICALP, Barcelona (J. DÃaz, Ed.), Springer LNCS 154, 39–51, 1983; expanded version: Theoret. Comput. Sci. 34 (1984) 135–156.
S.D. Brookes, C.A.R. Hoare, W. Roscoe, A Theory of Communicating Sequential Processes, J. Assoc. Comput. Mach. 31, No.3, 560–599.
J.A. Bergstra, J.W. Klop, Process algebra for synchronous communication, Inform. and Control 60 (1984) 109–137.
J.A. Bergstra, J.W. Klop, Algebra of communicating processes, in: J.W. de Bakker, M. Hazewinkel, J.K. Lenstra, Eds., Proc. CWI Symp. Math. and Comp. Sci., North-Holland, Amsterdam 1986.
J.A. Bergstra, J.W. Klop, The algebra of recursively defined processes and the algebra of regular processes, in: Proc. 11th ICALP, Antwerpen (J. Paredaens, Ed.), Springer LNCS 172, 82–94, 1984.
J.A. Bergstra, J.W. Klop, E.-R. Olderog, Readies and failures in the algebra of communicating processes, Report CS-R8523, Centre for Mathematics and Computer Science, Amsterdam 1985.
J.W. de Bakker, J.-J.Ch. Meyer, E.-R. Olderog, J.I. Zucker, Transition systems, infinitary languages and the semantics of uniform concurrency, in: Proc. 17th ACM STOC, Providence, R.I., 1985.
M.A. Harrison, Introduction to Formal Language Theory, Addison-Wesley 1978.
C.A.R. Hoare, A model for communicating sequential processes, in: "On the Construction of Programs" (R.M. McKeag and A.M. McNaughton, Eds.), 229–243, Cambridge Univ. Press, London/New York.
J.E. Hopcroft, J.D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley 1979.
A.J. Korenjak, J.E. Hopcroft, Simple deterministic languages, Proc. of 7th Annual Symposium on Switching and Automata Theory, Berkeley, 36–46, 1966.
J.-J.Ch. Meyer, Programming calculi based on fixed point transformations: semantics and applications, Ph.D. Thesis, Free University, Amsterdam 1985.
R. Milner, A calculus of communicating systems, Springer LNCS 92, 1980.
R. Milner, A complete inference system for a class of regular behaviours, J. Comput. and Syst. Sci. 28, 439–466, 1984.
D. Park, Concurrency and automata on infinite sequences, in: P. Deussen, Ed., Proc. 5th GI Conf. on Theor. Comp. Sci., Springer LNCS 104 (1981).
A. Salomaa, Computation and automata, Cambridge University Press 1985.
A. Salomaa, Formal languages, Academic Press, N.Y., 1973.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1987 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Baeten, J.C.M., Bergstra, J.A., Klop, J.W. (1987). Decidability of bisimulation equivalence for processes generating context-free languages. In: de Bakker, J.W., Nijman, A.J., Treleaven, P.C. (eds) PARLE Parallel Architectures and Languages Europe. PARLE 1987. Lecture Notes in Computer Science, vol 259. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-17945-3_5
Download citation
DOI: https://doi.org/10.1007/3-540-17945-3_5
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-17945-0
Online ISBN: 978-3-540-47181-3
eBook Packages: Springer Book Archive