Detail publikačního výsledku

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

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

Originální název

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

Anglický název

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

Druh

Stať ve sborníku v databázi WoS či Scopus

Originální abstrakt

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.

Anglický abstrakt

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.

Klíčová slova

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

Klíčová slova v angličtině

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

Autoři

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

Rok RIV

2025

Vydáno

12.08.2024

Nakladatel

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

Místo

Göttingen

Kniha

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

ISSN

2075-2180

Periodikum

Electronic Proceedings in Theoretical Computer Science, EPTCS

Svazek

407

Číslo

09

Stát

neuvedeno

Strany od

86

Strany do

99

Strany počet

14

URL

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

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

Dokumenty

metalinearness_submitted