Prof. RNDr. Alexander Meduna, CSc.

MEDUNA Alexander. Two-Way Metalinear PC Grammar Systems and Their Descriptional Complexity. Acta Cybernetica. 2004, roč. 2004, č. 16, s. 385-397. ISSN 0324-721X.
Jazyk publikace:angličtina
Název publikace:Two-Way Metalinear PC Grammar Systems and Their Descriptional Complexity
Název (cs):Dvousměrné metalineární PC gramatické systémy.
Strany:385-397
Kniha:Acta Informatica
Místo vydání:Szeged, HU
Rok:2004
Časopis:Acta Cybernetica, roč. 2004, č. 16, US
ISSN:0324-721X
Vydavatel:Szegedi Tudomanyegyetem
Klíčová slova
Dvousměrné metalineární PC gramatické systémy
Anotace
V tomto článku jsou zkoumány dvousměrné metalineární PC gramatické systémy a jejich popisná složitost.
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.
BibTeX:
@ARTICLE{
   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 = {http://www.fit.vutbr.cz/research/view_pub.php.cs?id=7341}
}

Vaše IPv4 adresa: 18.205.66.1
Přepnout na https