Přístupnostní navigace
E-přihláška
Vyhledávání Vyhledat Zavřít
Detail publikace
MEDUNA, A.
Originální název
Two-Way Metalinear PC Grammar Systems and Their Descriptional Complexity
Typ
článek v časopise - ostatní, Jost
Jazyk
angličtina
Originální abstrakt
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.
Klíčová slova
two-way metalinear PC grammar systems
Autoři
Rok RIV
2003
Vydáno
26. 2. 2004
Nakladatel
Szegedi Tudomanyegyetem
Místo
Szeged
ISSN
0324-721X
Periodikum
Acta Cybernetica
Ročník
2004
Číslo
16
Stát
Spojené státy americké
Strany od
385
Strany do
397
Strany počet
12
BibTex
@article{BUT42297, author="Alexandr {Meduna}", title="Two-Way Metalinear PC Grammar Systems and Their Descriptional Complexity", journal="Acta Cybernetica", year="2004", volume="2004", number="16", pages="385--397", issn="0324-721X" }