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
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
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"
}
Soubory
Nahoru