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

• Autorzy: Csuhaj-Varju E. , Mateescu A.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

cooperating distributed grammar systems; basic process algebra; process graph

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 73, nr 1-2
• Strony: 37--50
• Opis fizyczny: bibliogr. 13 poz.

Twórcy

autor

Csuhaj-Varju E.

autor

Mateescu A.

• Computer and Automation Research Institute, Hungarian Academy of Sciences, Kende u. 13-17, H-1111 Budapest, Hungary,

Bibliografia

• [1] J.C.M. Baeten, J.A. Bergstra, J.W. Klop: Decidability of bisimulation equivalence for processes generating context-free languages. In PARLE (J.W. de Bakker et al., eds.), Lecture Notes in Computer Science 259, Springer-Verlag, Berlin, 1987, 94-111.
• [2] J.C.M. Baeten, J.A. Bergstra, J.W. Klop: Decidability of bisimulation equivalence for processes generating context-free languages. Journal of the ACM, 40 (1993), 653-682.
• [3] P.M. Cohn: Universal Algebra. D. Reidel Publishing Company, New York, 1980.
• [4] S. Christensen, H. H¨uttel, C. Stirling: A polynomial algorithm for deciding bisimilarity of normed contextfree processes. Information and Control, 12 (1995), 143-148.
• [5] E. Csuhaj-Varjú, J. Dassow: On cooperating/distributed grammar systems. Journal of Information Processing and Cybernetics, EIK, 26 (1990), 49-63.
• [6] E. Csuhaj-Varjú, J. Dassow, J. Kelemen, Gh. P˘aun: Grammar Systems - A Grammatical Approach to Distribution and Cooperation.Gordon and Breach Science Publishers, Topics in ComputerMathematics 5, Yverdon, 1994.
• [7] E. Csuhaj-Varjú, Gy. Vaszil: An annotated bibliography of grammar systems. Available online at http://www.sztaki.hu/mms/bib.html
• [8] J. Dassow, V. Mitrana, Gh. P˘aun: Szilard languages associated to cooperating distributed grammar systems. Stud. Cerc. Matem., 45 (1993), 403-413.
• [9] J. Dassow, Gh. P˘aun, G. Rozenberg: Grammar systems. In Handbook of Formal Languages (G. Rozenberg, A. Salomaa, eds.), Springer-Verlag, Berlin, 1997, Vol 2, 155-213.
• [10] R. Meersman, G. Rozenberg: Cooperating grammar systems. In Proc. MFCS'78, Lecture Notes in Computer Science 64, Springer-Verlag, Berlin, 1978, 364-373.
• [11] G. Rozenberg, A. Salomaa, eds.: Handbook of Formal Languages Vol. 1-3, Springer-Verlag, Berlin, 1997.
• [12] R. Milner: A Calculus of Communicating Systems. Lecture Notes in Computer Science 92, Springer-Verlag, Berlin, 1980.
• [13] R. Paige, R.E. Tarjan: Three partition refinement algorithms. Siam Journal of Computing, 6 (1987), 973-989.