Detail publikace

Conclusive Tree-Controlled Grammars

KLOBUČNÍKOVÁ, D. KŘIVKA, Z. MEDUNA, A.

Originální název

Conclusive Tree-Controlled Grammars

Typ

článek ve sborníku ve WoS nebo Scopus

Jazyk

angličtina

Originální 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

Autoři

KLOBUČNÍKOVÁ, D.; KŘIVKA, Z.; MEDUNA, A.

Vydáno

26. 8. 2022

Nakladatel

School of Computer Science and Engineering, University of New South Wales

Místo

Debrecen

ISSN

2075-2180

Periodikum

Electronic Proceedings in Theoretical Computer Science, EPTCS

Číslo

367

Stát

neuvedeno

Strany od

112

Strany do

125

Strany počet

14

URL

http://eptcs.web.cse.unsw.edu.au/paper.cgi?NCMA2022.8

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