Publication Details

How to Demonstrate Metalinearness and Regularity by Tree-Restricted General Grammars

HAVEL Martin, KŘIVKA Zbyněk and MEDUNA Alexander. How to Demonstrate Metalinearness and Regularity by Tree-Restricted General Grammars. In: Proceedings 14th International Workshop on Non-Classical Models of Automata and Applications. Göttingen: School of Computer Science and Engineering, University of New South Wales, 2024, pp. 86-99. ISSN 2075-2180. Available from: https://cgi.cse.unsw.edu.au/~eptcs/paper.cgi?NCMA2024:3
Czech title
Jak dokázat metalinearitu a regulárnost pomocí stromově omezených obecných gramatik
Type
conference paper
Language
english
Authors
Havel Martin, Ing. (DIFS FIT BUT)
Křivka Zbyněk, Ing., Ph.D. (DIFS FIT BUT)
Meduna Alexander, prof. RNDr., CSc. (DIFS FIT BUT)
URL
Keywords

tree-restricted grammars, regulated grammars, metalinear grammars, k-linear grammars, regular grammars, context dependency, generative power

Abstract

This paper introduces derivation trees for general grammars. Within these trees, it defines context-dependent pairs of nodes, corresponding to rewriting two neighboring symbols using a non-context-free rule. It proves that the language generated by a linear core general grammar with a slow-branching derivation tree is k-linear if there is a constant u such that every sentence w in the generated language is the frontier of a derivation tree in which any pair of neighboring paths contains u or fewer context-dependent pairs of nodes. Next, it proves that the language generated by a general grammar with a regular core is regular if there is a constant u such that every sentence w in the generated language is the frontier of a derivation tree in which any pair of neighboring paths contains u or fewer context-dependent pairs of nodes. The paper explains that this result is a powerful tool for showing that certain languages are k-linear or regular.

Published
2024
Pages
86-99
Journal
Electronic Proceedings in Theoretical Computer Science, vol. 407, no. 9, ISSN 2075-2180
Proceedings
Proceedings 14th International Workshop on Non-Classical Models of Automata and Applications
Conference
14th International Workshop on Non-Classical Models of Automata and Applications, Göttingen, Germany, DE
Publisher
School of Computer Science and Engineering, University of New South Wales
Place
Göttingen, DE
DOI
10.4204/EPTCS.407.7
EID Scopus
2-s2.0-85205004625
BibTeX 
@INPROCEEDINGS{FITPUB13237,
   author = "Martin Havel and Zbyn\v{e}k K\v{r}ivka and Alexander Meduna",
   title = "How to Demonstrate Metalinearness and Regularity by Tree-Restricted General Grammars",
   pages = "86--99",
   booktitle = "Proceedings 14th International Workshop on Non-Classical Models of Automata and Applications",
   journal = "Electronic Proceedings in Theoretical Computer Science",
   volume = 407,
   number = 09,
   year = 2024,
   location = "G{\"{o}}ttingen, DE",
   publisher = "School of Computer Science and Engineering, University of New South Wales",
   ISSN = "2075-2180",
   doi = "10.4204/EPTCS.407.7",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/13237"
}
Back to top