Detail výsledku

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. no. 367, p. 112-125. ISSN: 2075-2180.
Typ
článek ve sborníku konference
Jazyk
anglicky
Autoři
Klobučníková Dominika, Ing., UIFS (FIT)
Křivka Zbyněk, Ing., Ph.D., UIFS (FIT)
Meduna Alexandr, prof. RNDr., CSc., UIFS (FIT)
Abstrakt

This paper presents a new approach to regulation of grammars. It divides
the derivation trees generated by grammars into two sectionsgenerative
and conclusive (the conclusion). The former encompasses generation of
symbols up till the moment when the lowest rightmost terminal of the
derivation tree is generated, whereas the latter represents the final
steps needed to successfully generate a sentence. A control mechanism
based on regulating only the conclusion is presented and subsequently
applied to tree-controlled grammars, creating conclusive tree-controlled
grammars. As the main result, it is shown that the ratio between depths
of generative and conclusive sections does not influence the generative
power. In addition, it is demonstrated that any recursively enumerable
language is generated by these grammars possessing no more than seven
nonterminals while the regulating language is union-free.

Klíčová slova

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

URL
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
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
Projekty
Efektivní konečné automaty pro automatické usuzování, MŠMT, ERC CZ, LL1908, zahájení: 2020-01-01, ukončení: 2024-12-31, ukončen
Metody AI pro zabezpečení kybernetického prostoru a řídicí systémy, VUT, Vnitřní projekty VUT, FIT-S-20-6293, zahájení: 2020-03-01, ukončení: 2023-02-28, ukončen
Výzkumné skupiny
Výzkumná skupina formálních modelů (VZ FM)
Pracoviště
Ústav informačních systémů (UIFS)
Nahoru