NONRETURNING PC GRAMMAR SYSTEMS CAN BE SIMULATED BY RETURNING SYSTEMS

Authors
DUMITRESCU S
Citation
S. Dumitrescu, NONRETURNING PC GRAMMAR SYSTEMS CAN BE SIMULATED BY RETURNING SYSTEMS, Theoretical computer science, 165(2), 1996, pp. 463-474
Citations number
12
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
Journal title
Theoretical computer science → ACNP
ISSN journal
03043975
Volume
165
Issue
2
Year of publication
1996
Pages
463 - 474
Database
ISI
SICI code
0304-3975(1996)165:2<463:NPGSCB>2.0.ZU;2-2
Abstract
One proves that the generative capacity of nonreturning parallel commu nicating (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.