Publication Details

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.
Czech title
Gramatiky s řízeným závěrem derivačního stromu
Type
conference paper
Language
English
Authors
Klobučníková Dominika, Ing.
Křivka Zbyněk, Ing., Ph.D. (DIFS)
Meduna Alexandr, prof. RNDr., CSc. (DIFS)
URL
Keywords

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

Abstract

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.

Published
2022
Pages
112–125
Journal
Electronic Proceedings in Theoretical Computer Science, EPTCS, no. 367, ISSN 2075-2180
Proceedings
Proceedings 12th International Workshop on Non-Classical Models of Automata and Applications
Conference
12th International Workshop on Non-Classical Models of Automata and Applications, Debrecen, HU
Publisher
School of Computer Science and Engineering, University of New South Wales
Place
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"
}
Files
Back to top