Detail publikace
Two-Way Metalinear PC Grammar Systems and Their Descriptional Complexity
Originální název
Two-Way Metalinear PC Grammar Systems and Their Descriptional Complexity
Anglický název
Two-Way Metalinear PC Grammar Systems and Their Descriptional Complexity
Jazyk
en
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.
Anglický 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{BUT42297,
author="Alexandr {Meduna}",
title="Two-Way Metalinear PC Grammar Systems and Their Descriptional Complexity",
annote="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.",
address="Szegedi Tudomanyegyetem",
booktitle="Acta Informatica",
chapter="42297",
institution="Szegedi Tudomanyegyetem",
journal="Acta Cybernetica",
number="16",
volume="2004",
year="2004",
month="february",
pages="385--397",
publisher="Szegedi Tudomanyegyetem",
type="journal article - other"
}