Publication Details
Two-Way Metalinear PC Grammar Systems and Their Descriptional Complexity
two-way metalinear PC grammar systems
A discussion of two-way metalinear PC grammar systems and their descriptional complexity.
Besides a derivation step and a communication step, a two-way PC grammar sytem can make a reduction step during which it reduces the right-hand side of a context-free production to its left hand-side. This paper proves that every non-unary recursively enumerable language is defined by a centralized two-way grammar system, \Gamma, with two metalinear componets in a very economical way. Indeed, \Gamma's master has only three nonterminals and one communication production; furthermore, it produces all sentential forms with no more than two occurances of nonterminals. In addition, during every computation, \Gamma makes a single communication step. Some variants of two-way PC grammar systems are discussed in the conclusion of the paper.
@ARTICLE{FITPUB7341, author = "Alexander Meduna", title = "Two-Way Metalinear PC Grammar Systems and Their Descriptional Complexity", pages = "385--397", booktitle = "Acta Informatica", journal = "Acta Cybernetica", volume = 2004, number = 16, year = 2004, location = "Szeged, HU", publisher = "Szegedi Tudomanyegyetem", ISSN = "0324-721X", language = "english", url = "https://www.fit.vut.cz/research/publication/7341" }