Two-Way Linear PC Grammar Systems

Result code in IS VaVaI

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

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

Two-Way Linear PC Grammar Systems

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

Czech name

Dvousměrné lineární PC gramatické systémy

Czech description

Kromě derivačních a komunikačních kroků může dvousměrný PC gramatický systém vykonávat kroky redukční během nichž nahradí pravou stranu bezkontextového pravidla stranou levou. Článek dokazuje, že každý neunární rekurzivně spočetný jazyk je definován úsporným způsobem pomocí centralizovaného dvousměrného PC gramatického systému, &amp;Gamma;, který má pět komponent. Hlavní komponenta obsahuje pouze tři nonterminály a jediné praviddlo obsahující komunikační symbol; dále všechny generované větné formy neobssahují více než dva výskyty nonterminálních symbolů. Během každého výpočtu provede &amp;Gamma; jediný komunikační krok.

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 8th Spring International Conference ISIM'05 Information Systems Implementation and Modelling

ISBN

80-86840-09-3

ISSN

—

e-ISSN

—

Number of pages

8

Pages from-to

87-94

Publisher name

NEUVEDEN

Place of publication

Ostrava

Event location

Hradec nad Moravicí

Event date

Apr 19, 2005

Type of event by nationality

EUR - Evropská akce

UT code for WoS article

—