Detail publikace

Conclusive Tree-Controlled Grammars

KLOBUČNÍKOVÁ Dominika, KŘIVKA Zbyněk a MEDUNA Alexander. Conclusive Tree-Controlled Grammars. In: Proceedings 12th International Workshop on Non-Classical Models of Automata and Applications . Debrecen: School of Computer Science and Engineering, University of New South Wales, 2022, s. 112-125. ISSN 2075-2180. Dostupné z: http://eptcs.web.cse.unsw.edu.au/paper.cgi?NCMA2022.8
Název česky
Gramatiky s řízeným závěrem derivačního stromu
Typ
článek ve sborníku konference
Jazyk
angličtina
Autoři
Klobučníková Dominika, Ing. (UIFS FIT VUT)
Křivka Zbyněk, Ing., Ph.D. (UIFS FIT VUT)
Meduna Alexander, prof. RNDr., CSc. (UIFS FIT VUT)
URL
Abstrakt

Příspěvek prezentuje nový přístup k řízení gramatik, kde rozděluje derivační stromy generované těmito gramatikami na dvě části: (1) generující a (2) závěrečná. Část (1) zahrnuje symboly generované do momentu vygenerování nejspodnějšího nejpravějšího terminálu v derivačním stromu, zatímco (2) reprezentuje závěrečné kroky potřebné pro úspěšné vygenerování věty (tj. řetězce bez neterminálů). Je představen mechanismus řízení pouze závěrečné části derivačního stromu, který je aplikován na gramatiky s řízeným derivačním stromem, které nazýváme gramatiky s řízeným závěrem derivačního stromu. Příspěvek jako hlavní výsledek ukazuje, že poměr hloubek generující a závěrečné části neovlivňuje generativní sílu modelu. Navíc je ukázáno, že každý rekurzivně spočetný jazyk je generován těmito gramatikami pouze se sedmi neterminály, zatímco je řídicí jazyk regulární bez operace sjednocení.

Rok
2022
Strany
112-125
Časopis
Electronic Proceedings in Theoretical Computer Science, č. 367, ISSN 2075-2180
Sborník
Proceedings 12th International Workshop on Non-Classical Models of Automata and Applications
Konference
12th International Workshop on Non-Classical Models of Automata and Applications, Debrecen, HU
Vydavatel
School of Computer Science and Engineering, University of New South Wales
Místo
Debrecen, HU
DOI
10.4204/EPTCS.367.8
EID Scopus
2-s2.0-85137563410
BibTeX 
@INPROCEEDINGS{FITPUB12771,
   author = "Dominika Klobu\v{c}n\'{i}kov\'{a} and Zbyn\v{e}k K\v{r}ivka and Alexander Meduna",
   title = "Conclusive Tree-Controlled Grammars",
   pages = "112--125",
   booktitle = "Proceedings 12th International Workshop on Non-Classical Models of Automata and Applications ",
   journal = "Electronic Proceedings in Theoretical Computer Science",
   number = 367,
   year = 2022,
   location = "Debrecen, HU",
   publisher = "School of Computer Science and Engineering, University of New South Wales",
   ISSN = "2075-2180",
   doi = "10.4204/EPTCS.367.8",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/12771"
}
Nahoru