Publication Details

Two-Way Metalinear PC Grammar Systems and Their Descriptional Complexity

MEDUNA Alexander. Two-Way Metalinear PC Grammar Systems and Their Descriptional Complexity. Acta Cybernetica, vol. 2004, no. 16, pp. 385-397. ISSN 0324-721X.
Czech title
Dvousměrné metalineární PC gramatické systémy.
Type
journal article
Language
english
Authors
Meduna Alexander, prof. RNDr., CSc. (DIFS FIT BUT)
Keywords

two-way metalinear PC grammar systems

Abstract

A discussion of two-way metalinear PC grammar systems and their descriptional complexity.

Annotation

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.

Published
2004
Pages
385-397
Journal
Acta Cybernetica, vol. 2004, no. 16, ISSN 0324-721X
Book
Acta Informatica
Publisher
Szegedi Tudomanyegyetem
Place
Szeged, HU
BibTeX 
@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"
}
Back to top