Detail publikace

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

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

Originální název

Typ

článek ve sborníku ve WoS nebo Scopus

Jazyk

angličtina

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.

Klíčová slova

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.

Vydáno

12. 8. 2024

Nakladatel

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

Místo

Göttingen

ISSN

2075-2180

Periodikum

Electronic Proceedings in Theoretical Computer Science, EPTCS

Ročník

407

Číslo

Stát

neuvedeno

Strany od

Strany do

Strany počet

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.pdf

Odpovědnost: Ing. Marek Strakoš