Affiliations: Research Group on Mathematical Linguistics, Rovira i
Virgili University Pl. Imperial Tárraco 1, 43005 Tarragona, Spain.
E-mail: mariaadela.grando@estudiants.urv.es | Faculty of Mathematics and Computer Science,
University of Bucharest Str. Academiei 14, 70109 Bucharest, Romania. E-mail:
vmi@fll.urv.es
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
