Two-way PC Grammar Systems Based on Regular Grammars
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F04%3APU49091" target="_blank" >RIV/00216305:26230/04:PU49091 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Two-way PC Grammar Systems Based on Regular Grammars
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, &Gamma;, with three components in a very economical way. Indeed, &Gamma;'s master has only three nonterminals and one communication production; furthermore, it produces all sententiall forms with no more than two occurrences of nonterminals. In addition, during every computation, &Gamma; makes a single communication step. Some variants of two-way PC grammar system are discussed in the conclusion of this paper.
Czech name
Dvousměrné PC gramatické systémy složené z regulárních gramatik
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, &Gamma;, s třemi komponentami. Přičemž hlavní komponenta obsahuje pouze tři nontermilány a jediné pravidlo obsahující komunikační symbol. Dále &Gamma; během každého výpočttu provede jediný komunikační krok a všechny větné formy obsahují maximálně dva výskyty nonterminálních symbolů. Na závěr článku jsou diskutovány některé varianty těchto systémů.
Classification
Type
D - Article in proceedings
CEP classification
JC - Computer hardware and software
OECD FORD branch
—
Result continuities
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)
Others
Publication year
2004
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of 7th International Conference ISIM'04 Information Systems Implementation and Modeling
ISBN
80-85988-99-2
ISSN
—
e-ISSN
—
Number of pages
8
Pages from-to
111-118
Publisher name
NEUVEDEN
Place of publication
Ostrava
Event location
Rožnov pod Radhošťem
Event date
Apr 19, 2004
Type of event by nationality
EUR - Evropská akce
UT code for WoS article
—