Detail publikace

Conclusive Tree-Controlled Grammars

KLOBUČNÍKOVÁ, D.; KŘIVKA, Z.; MEDUNA, A. Conclusive Tree-Controlled Grammars. In Proceedings 12th International Workshop on Non-Classical Models of Automata and Applications. Electronic Proceedings in Theoretical Computer Science, EPTCS. Debrecen: School of Computer Science and Engineering, University of New South Wales, 2022. p. 112-125. ISSN: 2075-2180.
Název česky
Gramatiky s řízeným závěrem derivačního stromu
Typ
článek ve sborníku konference
Jazyk
anglicky
Autoři
Klobučníková Dominika, Ing.
Křivka Zbyněk, Ing., Ph.D. (UIFS)
Meduna Alexandr, prof. RNDr., CSc. (UIFS)
URL
Klíčová slova

Tree-controlled grammar, Conclusive tree-controlled grammar, Computational completeness, Derivation tree, Sub-regular language families, Descriptional complexity

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, EPTCS, č. 367, ISSN 2075-2180
Sborník
Proceedings 12th International Workshop on Non-Classical Models of Automata and Applications
Vydavatel
School of Computer Science and Engineering, University of New South Wales
Místo
Debrecen
DOI
10.4204/EPTCS.367.8
UT WoS
001047943700009
EID Scopus
2-s2.0-85137563410
BibTeX 
@inproceedings{BUT178927,
  author="Dominika {Klobučníková} and Zbyněk {Křivka} and Alexandr {Meduna}",
  title="Conclusive Tree-Controlled Grammars",
  booktitle="Proceedings 12th International Workshop on Non-Classical Models of Automata and Applications",
  year="2022",
  journal="Electronic Proceedings in Theoretical Computer Science, EPTCS",
  number="367",
  pages="112--125",
  publisher="School of Computer Science and Engineering, University of New South Wales",
  address="Debrecen",
  doi="10.4204/EPTCS.367.8",
  issn="2075-2180",
  url="http://eptcs.web.cse.unsw.edu.au/paper.cgi?NCMA2022.8"
}
Nahoru