On the power of parallel communicating grammar systems with right-linear components. (English) Zbl 0892.68058

Summary: We settle here two problems concerning the generative power of parallel communicating grammar systems with right-linear components: (1) each linear language can be generated by a non-centralized returning system, (2) the family of languages generated by centralized returning systems is incomparable with the family of languages generated by non-returning centralized systems. It is also proved that centralized returning systems with right-linear components are strictly more powerful than systems with regular rules in the restricted sense.


68Q42 Grammars and rewriting systems
Full Text: DOI EuDML


[1] 1. L. CAI, The computational complexity of PCGS with regular components, Proc. of Developments in Language Theory Conf., Magdeburg, 1995. Zbl1096.68640 · Zbl 1096.68640
[2] 2. E. CSUHAJ-VARJU, J. DASSOW, J. KELEMEN and Gh. PĂUN, Grammar Systems. A Grammatical Approach to Distribution and Cooperation, Gordon and Breach, London, 1994. Zbl0925.68286 MR1475215 · Zbl 0925.68286
[3] 3. J. DASSOW and Gh. PĂUN, Regulated Rewriting in Formal Language Theory, Springer, Berlin, Heidelberg, 1989. Zbl0697.68067 MR1067543 · Zbl 0697.68067
[4] 4. J. DASSOW, Gh. PĂUN and G. ROZENBERG, Generating languages in a distributed way: Grammar Systems, in Handbook of Formal Languages (G.Rozenberg, A. Salomaa, eds.), Springer-Verlag, Berlin, Heidelberg, 1997. MR1470009
[5] 5. S. DUMITRESCU, Non-returning PC grammar systems can be simulated by returning systems, Theoretical Computer Sci., 1996, 165, pp. 463-474. Zbl0872.68099 MR1411896 · Zbl 0872.68099 · doi:10.1016/0304-3975(95)00258-8
[6] 6. S. DUMITRESCU, Gh. PĂUN and A. SALOMAA, Pattern languages versus parallel communicating grammar systems, Intern. J. Found. Computer Sci., to appear. Zbl0870.68096 · Zbl 0870.68096 · doi:10.1142/S0129054197000057
[7] 7. S. GINSBURG, The Mathematical Theory of Context-free Languages, McGraw Hill Book Comp., New York, 1996. Zbl0184.28401 MR211815 · Zbl 0184.28401
[8] 8. D. HAUSCHILD and M. JANTZEN, Petri nets algorithms in the theory of matrix grammars, Acta Informatica, 1994, 31, pp. 719-728. Zbl0834.68064 MR1306096 · Zbl 0834.68064 · doi:10.1007/BF01178731
[9] 9. V. MIHALACHE, Matrix grammars versus parallel communicating grammar systems, in vol. Mathematical Aspects of Natural and Formal Languages (Gh. PfUN, ed.), World Sci. Publ., Singapore, 1994, pp. 293-318.
[10] 10. V. MIHALACHE, On the generative capacity of parallel communicating grammar systems with regular components, Computers and AI, 1996, 75, pp. 155-172. Zbl0852.68045 MR1405409 · Zbl 0852.68045
[11] 11. Gh. PĂUN and L. SÂNTEAN, Parallel communicating grammar systems: the regular case, Ann. Univ. Buc., Series Matem.-Inform., 1989, 38, pp. 55-63. Zbl0749.68048 MR1100348 · Zbl 0749.68048
[12] 12. A. SALOMAA, Formal Languages, Academic Press, New York, 1973. Zbl0262.68025 MR438755 · Zbl 0262.68025
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.