Bidirectional Contextual Grammars
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F06%3APU73550" target="_blank" >RIV/00216305:26230/06:PU73550 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Bidirectional Contextual Grammars
Original language description
The present paper introduces and discusses bidirectional contextual grammars as a straightforward generalization of externally generating contextual grammars without choice. In essence, besides ordinary derivation steps, the bidirectional contextual grammars can also make reduction steps, which shorten the rewritten strings. This paper demonstrates that these grammars characterize the family of recursively enumerable languages. In fact, this characterization holds even in terms of one-turn bidirectionalcontextual grammars, which can change derivations steps to reduction steps during the generation process no more than once. <br>
Czech name
Obousměrné kontextuální gramatiky
Czech description
Práce zavádí obousměrné kontextuální gramatiky jako přímočaré zobecnění externích kontextuálních gramatik bez výběru. Tyto gramatiky provádějí kromě derivačních kroků také redukční kroky, které zkracují derivovaný řetězec. V práci je ukázáno, že tyto gramatiky dosahují síly rekurzivně spočetných jazyků. Navíc je ukázáno, že lze výsledku dosáhnout s použitím jednoobrátkových obousměrných kontextuálních gramatik, jež provádějí změnu z derivačních kroků na redukční nejvýše jednou.
Classification
Type
D - Article in proceedings
CEP classification
BD - Information theory
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
2006
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 1st International Workshop WFM '06
ISBN
80-86840-20-4
ISSN
—
e-ISSN
—
Number of pages
8
Pages from-to
61-68
Publisher name
NEUVEDEN
Place of publication
Přerov
Event location
Přerov
Event date
Apr 25, 2006
Type of event by nationality
EUR - Evropská akce
UT code for WoS article
—