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
Meduna Alexander, prof. RNDr., CSc. (UIFS FIT VUT)
Techet Jiří, Ing., Ph.D. (UIFS FIT VUT)
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