How to Demonstrate Metalinearness and Regularity by Tree-Restricted General Grammars
<|reference_start|>How to Demonstrate Metalinearness and Regularity by Tree-Restricted General Grammars: 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.<|reference_end|>
@article{havel2024how,
    title={How to Demonstrate Metalinearness and Regularity by Tree-Restricted
  General Grammars},
    author={Martin Havel (Brno University of Technology, Faculty of Information
  Technology), Zbynv{e}k Kv{r}ivka (Brno University of Technology, Faculty of
  Information Technology), Alexander Meduna (Brno University of Technology,
  Faculty of Information Technology)},
    journal={EPTCS 407, 2024, pp. 86-99},
    year={2024},
    doi={10.4204/EPTCS.407.7},
    archivePrefix={arXiv},
    eprint={2409.06972},
    primaryClass={cs.FL}
}