A Possible Connection Between Two Theories: Grammar Systems and Concurrent Programming
Titel:
A Possible Connection Between Two Theories: Grammar Systems and Concurrent Programming
Auteur:
Grando, María Adela Mitrana, Victor
Verschenen in:
Fundamenta informaticae
Paginering:
Jaargang 76 (2007) nr. 3 pagina's 325-336
Jaar:
2007-03-15
Inhoud:
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.