A Possible Connection Between Two Theories: Grammar Systems and Concurrent Programming

Issue title: SPECIAL ISSUE ON DEVELOPMENTS IN GRAMMAR SYSTEMS

Article type: Research Article

Authors: Grando, María Adela | Mitrana, Victor

Affiliations: Research Group on Mathematical Linguistics, Rovira i Virgili University Pl. Imperial Tárraco 1, 43005 Tarragona, Spain. E-mail: [email protected] | Faculty of Mathematics and Computer Science, University of Bucharest Str. Academiei 14, 70109 Bucharest, Romania. E-mail: [email protected]

Abstract: The aim of this note is to show how parallel communicating grammar systems and concurrent programs might be viewed as related models for distributed and cooperating computation. We argue that a grammar system can be translated into a concurrent program, where one can make use of the Owicki-Gries theory and other tools available in the theory of concurrent programming. The converse translation is also possible and this turns out to be useful when we are looking for a grammar system able to generate a given language. In order to show this, we use the language: L_{cd} = {a^nb^mc^nd^m∣ n,m ⩾ 1}, called crossed agreement language, one of the basic non-context free constructions in natural and artificial languages. We prove, using tools from concurrent programming theory, that L_{cd} can be generated by a nonreturning parallel communicating grammar system with three regular components. We also discuss the absence of strategies in the concurrent programming theory to prove that L_{cd} cannot be generated by any parallel communicating grammar system with two regular components only, no matter the working strategy, but we prove this statement in the grammar system framework.

Keywords: Parallel communicating grammar system, multiprogramming, Owicki-Gries theory

Journal: Fundamenta Informaticae, vol. 76, no. 3, pp. 325-336, 2007