Publication detail
How to Demonstrate Metalinearness and Regularity by Tree-Restricted General Grammars
HAVEL, M. KŘIVKA, Z. MEDUNA, A.
Original Title
How to Demonstrate Metalinearness and Regularity by Tree-Restricted General Grammars
Type
conference paper
Language
English
Original 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.
Keywords
tree-restricted grammars, regulated grammars, metalinear grammars, k-linear grammars, regular grammars, context dependency, generative power
Authors
HAVEL, M.; KŘIVKA, Z.; MEDUNA, A.
Released
12. 8. 2024
Publisher
School of Computer Science and Engineering, University of New South Wales
Location
Göttingen
ISBN
2075-2180
Periodical
Electronic Proceedings in Theoretical Computer Science, EPTCS
Year of study
407
Number
09
State
unknown
Pages from
86
Pages to
99
Pages count
14
URL
BibTex
@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"
}
Documents
Responsibility: Ing. Marek Strakoš