A Possible Connection Between Two Theories: Grammar Systems and Concurrent Programming
Title:
A Possible Connection Between Two Theories: Grammar Systems and Concurrent Programming
Author:
Grando, María Adela Mitrana, Victor
Appeared in:
Fundamenta informaticae
Paging:
Volume 76 (2007) nr. 3 pages 325-336
Year:
2007-03-15
Contents:
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.
Journal description