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

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F24%3APU151679" target="_blank" >RIV/00216305:26230/24:PU151679 - isvavai.cz</a>

Výsledek na webu

<a href="https://cgi.cse.unsw.edu.au/~eptcs/paper.cgi?NCMA2024:3" target="_blank" >https://cgi.cse.unsw.edu.au/~eptcs/paper.cgi?NCMA2024:3</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.4204/EPTCS.407.7" target="_blank" >10.4204/EPTCS.407.7</a>

Jazyk výsledku

angličtina

Název v původním jazyce

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

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

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

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2024

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

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

ISBN

—

ISSN

2075-2180

e-ISSN

—

Počet stran výsledku

14

Strana od-do

86-99

Název nakladatele

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

Místo vydání

Göttingen

Místo konání akce

Göttingen, Germany

Datum konání akce

12. 8. 2024

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—