Detail publikace

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

MEDUNA, A.; TECHET, J. 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: University of Pavol Jozef Šafárik, 2007. p. 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
anglicky
Autoři
Meduna Alexandr, prof. RNDr., CSc. (UIFS)
Techet Jiří, Ing., Ph.D.
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
ISBN
978-80-7097-688-3
Vydavatel
University of Pavol Jozef Šafárik
Místo
High Tatras
BibTeX 
@inproceedings{BUT28797,
  author="Alexandr {Meduna} and Jiří {Techet}",
  title="Reduction of Scattered Context Generators of Sentences Preceded by Their Leftmost Parses",
  booktitle="Proceedings of 9th International Workshop on Descriptional Complexity of Formal Systems",
  year="2007",
  pages="178--185",
  publisher="University of Pavol Jozef Šafárik",
  address="High Tatras",
  isbn="978-80-7097-688-3"
}
Nahoru