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