Two-Way Linear PC Grammar Systems and Their Descriptional Complexity

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F05%3APU56397" target="_blank" >RIV/00216305:26230/05:PU56397 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

Two-Way Linear PC Grammar Systems and Their Descriptional Complexity

Original language description

Besides derivation and communication steps, a two-way PC grammar system 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, &amp;#915;, with five components in a very economical way. Indeed, &amp;#915;'s master has only three nonterminals and one communication production; furthermore, it produces all sentential foorms with no more than two occurrences of nonterminals. In addition, during every computation, &amp;#915; makes a single communication step.

Czech name

Dvousměrné lineární PC gramatické systémy a jejich popisná složitost

Czech description

Kromě derivačních a komunikačních kroků dvousměrný PC gramatický systém vykonává také krok redukční, během kterého se nahrazuje pravá strana bezkontextového pravidla stranou levou. Článek dokazuje, že každý neunární rekurzivně spočetný jazyk může být popsán úsporným způsobem centralizovaným dvousměrným PC gramatickým systémem, &amp;#915;, s pěti komponentami. Přičemž hlavní komponenta obsahuje pouze tři nontermilány a jediné pravidlo obsahující komunikační symbol. Dále &amp;#915; během každého výpočtu pprovede jediný komunikační krok a všechny větné formy obsahují maximálně dva výskyty nonterminálních symbolů.

Type

D - Article in proceedings

CEP classification

JC - Computer hardware and software

OECD FORD branch

—

Project

<a href="/en/project/GA201%2F04%2F0441" target="_blank" >GA201/04/0441: Optimally integrated models of modern information technologies</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2005

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Proceedings of the 11th Conference Student EEICT 2005

ISBN

80-214-2890-2

ISSN

—

e-ISSN

—

Number of pages

5

Pages from-to

546-550

Publisher name

Publishing house of Brno University of Technology VUTIUM

Place of publication

Brno

Event location

Brno

Event date

Apr 28, 2005

Type of event by nationality

CST - Celostátní akce

UT code for WoS article

—