Detail – FFA BUT

Original Title

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

English Title

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

Type

Paper in proceedings (conference paper)

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.

English 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

Key words in English

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

Authors

HAVEL, M.; KŘIVKA, Z.; MEDUNA, A.

RIV year

2025

Released

12.08.2024

Publisher

School of Computer Science and Engineering, University of New South Wales

Location

Göttingen

Book

Proceedings 14th International Workshop on Non-Classical Models of Automata and Applications

ISBN

2075-2180

Periodical

Electronic Proceedings in Theoretical Computer Science, EPTCS

Volume

407

Number

09

State

unknown

Pages from

86

Pages to

99

Pages count

14

URL

https://cgi.cse.unsw.edu.au/~eptcs/paper.cgi?NCMA2024:3

Full text in the Digital Library

http://hdl.handle.net/

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

metalinearness_submitted