A 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%3APU49114" target="_blank" >RIV/00216305:26230/04:PU49114 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
A 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, &#915;, with three components in a very economical way. Indeed, &#915;?s master has only three nonterminals and one communication production; furthermore, it produces all sentential fforms with no more than two occurrences of nonterminals. In addition, during every computation, &#915; 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 založené na regulárních gramatikách
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, &#915;, který má tři komponenty. 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 &#915; jediný komunikační krok. 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 10th Conference and Competition STUDENT EEICT 2004
ISBN
80-214-2635-7
ISSN
—
e-ISSN
—
Number of pages
5
Pages from-to
252-256
Publisher name
Faculty of Information Technology BUT
Place of publication
Brno
Event location
Brno
Event date
Apr 29, 2004
Type of event by nationality
CST - Celostátní akce
UT code for WoS article
—