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

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 ^n b ^m c ^n d ^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.