A possible connection between two theories: Grammar systems and concurrent programming
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) vertical bar n, m >= }, 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 non-retuming 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.
parallel communicating grammar system owicki-gries theory multiprogramming