Publication Details
How to Demonstrate Metalinearness and Regularity by Tree-Restricted General Grammars
Křivka Zbyněk, Ing., Ph.D. (DIFS)
Meduna Alexandr, prof. RNDr., CSc. (DIFS)
tree-restricted grammars, regulated grammars, metalinear grammars, k-linear grammars, regular grammars, context dependency, generative power
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.
@inproceedings{BUT189042,
author="Martin {Havel} and Zbyněk {Křivka} and Alexandr {Meduna}",
title="How to Demonstrate Metalinearness and Regularity by Tree-Restricted General Grammars",
booktitle="Proceedings 14th International Workshop on Non-Classical Models of Automata and Applications",
year="2024",
journal="Electronic Proceedings in Theoretical Computer Science, EPTCS",
volume="407",
number="09",
pages="86--99",
publisher="School of Computer Science and Engineering, University of New South Wales",
address="Göttingen",
doi="10.4204/EPTCS.407.7",
issn="2075-2180",
url="https://cgi.cse.unsw.edu.au/~eptcs/paper.cgi?NCMA2024:3"
}