Reduction of Scattered Context Generators of Sentences Preceded by Their Leftmost Parses

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F07%3APU70815" target="_blank" >RIV/00216305:26230/07:PU70815 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
Reduction of Scattered Context Generators of Sentences Preceded by Their Leftmost Parses
Original language description
This paper uses scattered context grammars to derive their sentences preceded by corresponding parses--the sequences of labels of productions used during the derivation. It discusses their canonical versions, which make this derivation in a leftmost way,and demonstrates that for every recursively enumerable language, L, there exists a scattered context generator whose language consists of L's sentences preceded by their leftmost parses. In fact, this demonstration is achieved based on generators with areduced number of nonterminals.<br>
Czech name
Redukce generátorů vět předcházených jejich nejlevějšími rozbory
Czech description
V této práci jsou použity gramatiky s rozptýleným kontextem ke generování vět předcházených odpovídajícími rozbory --  sekvencemi návěští pravidel použitých během derivace. Jsou diskutovány jejich kanonické verze, které provádějí derivace nejlevějším způsobem, a dále je demonstrováno, že pro každý rekurzivně spočetný jazyk L existuje gramatika s rozptýleným kontextem jejíž jazyk je složen z vět L předcházených jejich nejlevějšími rozbory. Navíc je tato charakterizace dosažena pomocí gramatik s redukovaným počtem nonterminálů.<br>

Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year
2007
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 9th International Workshop on Descriptional Complexity of Formal Systems
ISBN
978-80-7097-688-3
ISSN
—
e-ISSN
—
Number of pages
8
Pages from-to
178-185
Publisher name
University of Pavol Jozef Šafárik
Place of publication
High Tatras
Event location
High Tatras
Event date
Jul 20, 2007
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—

Similar results(10)