×

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.

MSC:

68Q42 Grammars and rewriting systems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Cai, L., The computational complexity of PCGS with regular components, (Proc. Developments in Language Theory Conf.. Proc. Developments in Language Theory Conf., Magdeburg (1995)) · 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: 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.; S. Dumitrescu and Gh. Păun, On the power of parallel communicating grammar systems with right-linear components, submitted. · Zbl 0892.68058
[4] Freund, R.; Păun, Gh.; Procopiuc, C. M.; Procopiuc, O., Parallel communicating grammar systems with context-sensitive components, (Păun, Gh., Artificial Life. Grammatical Models (1995), The Black Sea Univ. Press: The Black Sea Univ. Press Bucharest) · Zbl 0847.68061
[5] Hromkovic, J., Descriptional and computational complexity measures for distributive generation of languages, (Proc. of Developments in Language Theory Conf.. Proc. of Developments in Language Theory Conf., Magdeburg (1995))
[6] Hromkovic, J.; Kari, J.; Kari, L.; Pradubska, D., Two lower bounds on distributive generation of languages, (Proc. MFCS 94, LNCS 841 (1994), Springer: Springer Berlin), 423-432 · Zbl 1493.68146
[7] Mihalache, V., On parallel communicating grammar systems with context-free components, (Păun, Gh., Mathematical Linguistics and Related Topics (1995), The Publ. House of the Romanian Academy: The Publ. House of the Romanian Academy Bucharest), 258-270
[8] D. Pardubska, Communication complexity hierarchies for distributive generation of languages, Fundamenta Informaticae; D. Pardubska, Communication complexity hierarchies for distributive generation of languages, Fundamenta Informaticae
[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: 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.; 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. 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.