On a Connection Between Cooperating Distributed Grammar Systems and Basic Process Algebra

Issue title: SPECIAL ISSUE ON TRAJECTORIES OF LANGUAGE THEORY Dedicated to the memory of Alexandru Mateescu

Article type: Research Article

Authors: Csuhaj-Varjú, Erzsébet | Mateescu, Alexandru

Affiliations: Computer and Automation Research Institute, Hungarian Academy of Sciencesm Kende utca 13–17, H-1111 Budapest, Hungary. E-mail: csuhaj@sztaki.hu

Abstract: In this paper we discuss some relationships between cooperating distributed (CD) grammar systems and the basic process algebra (BPA) calculus. We associate different types of process graphs from this calculus to CD grammar systems which describe the behavior of the components of the system under cooperation. We prove that these process graphs form a subalgebra of the graph model of BPA. It is also shown that for certain restricted variants of CD grammar systems and for certain types of these process graphs the bisimilarity of two process graphs is decidable.

Keywords: Cooperating distributed grammar systems, basic process algebra, process graph

Journal: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 37-50, 2006