Detail publikace

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

MEDUNA Alexander a TECHET Jiří. Reduction of Scattered Context Generators of Sentences Preceded by Their Leftmost Parses. In: Proceedings of 9th International Workshop on Descriptional Complexity of Formal Systems. High Tatras: Univerzita Pavla Jozefa Šafárika v Košiciach, 2007, s. 178-185. ISBN 978-80-7097-688-3.
Název česky
Redukce generátorů vět předcházených jejich nejlevějšími rozbory
Typ
článek ve sborníku konference
Jazyk
angličtina
Autoři
Klíčová slova

gramatiky s rozptýleným kontextem, kanonické derivace, rozbory, popisná složitost

Abstrakt

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ů.

Rok
2007
Strany
178-185
Sborník
Proceedings of 9th International Workshop on Descriptional Complexity of Formal Systems
Konference
9th International Workshop on Descriptional Complexity of Formal Systems, High Tatras, SK
ISBN
978-80-7097-688-3
Vydavatel
Univerzita Pavla Jozefa Šafárika v Košiciach
Místo
High Tatras, SK
BibTeX
@INPROCEEDINGS{FITPUB8361,
   author = "Alexander Meduna and Ji\v{r}\'{i} Techet",
   title = "Reduction of Scattered Context Generators of Sentences Preceded by Their Leftmost Parses",
   pages = "178--185",
   booktitle = "Proceedings of 9th International Workshop on Descriptional Complexity of Formal Systems",
   year = 2007,
   location = "High Tatras, SK",
   publisher = "University of Pavol Jozef \v{S}af\'{a}rik",
   ISBN = "978-80-7097-688-3",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/8361"
}
Nahoru