Nonreturning PC grammar systems can be simulated by returning systems. (English) Zbl 0872.68099

Summary: One proves that the generative capacity of nonreturning parallel communicating (PC) grammar systems with context-free rules, centralized or not, does not overpass that of the noncentralized returning PC grammar systems. This strengthens previous results in this area and clarifies the returning-nonreturning relationship.


68Q42 Grammars and rewriting systems
Full Text: DOI


[1] Cai, L., The computational complexity of PCGS with regular components, () · Zbl 1096.68640
[2] Csuhaj-Varju; Dassow, J.; Kelemen, J.; Păun, Gh., Grammar systems. A grammatical approach to distribution and cooperation, (1994), Gordon and Breach London · Zbl 0925.68286
[3] S. Dumitrescu and Gh. Păun, On the power of parallel communicating grammar systems with right-linear components, submitted.
[4] Freund, R.; Păun, Gh.; Procopiuc, C.M.; Procopiuc, O., Parallel communicating grammar systems with context-sensitive components, () · Zbl 0847.68061
[5] Hromkovic, J., Descriptional and computational complexity measures for distributive generation of languages, ()
[6] Hromkovic, J.; Kari, J.; Kari, L.; Pradubska, D., Two lower bounds on distributive generation of languages, (), 423-432
[7] Mihalache, V., On parallel communicating grammar systems with context-free components, (), 258-270
[8] D. Pardubska, Communication complexity hierarchies for distributive generation of languages, Fundamenta Informaticae, to appear.
[9] Păun, Gh.; Sântean, L., Parallel communicating grammar systems: the regular case, Ann. univ. buc., ser. matem.-inform., 38, 55-63, (1989) · Zbl 0749.68048
[10] Procopiuc, O.; Ionescu, C.M.; Tiplea, F.L., Parallel communicating grammar systems: the contextsensitive case, Internat. J. comput. math., 49, 145-156, (1993) · Zbl 0807.68063
[11] Salomaa, A., Formal languages, (1973), Academic Press New York · Zbl 0262.68025
[12] G. Vaszil, The simulation of a non-returning parallel communicating grammar system with a returning system in case of linear component grammars, submitted.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.