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

Result code in 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>

Result on the web

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

Result language

angličtina

Original language name

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

Original language description

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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

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

Project

—

Continuities

S - Specificky vyzkum na vysokych skolach

Publication year

2024

Confidentiality

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

Article name in the collection

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

ISBN

—

ISSN

2075-2180

e-ISSN

—

Number of pages

14

Pages from-to

86-99

Publisher name

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

Place of publication

Göttingen

Event location

Göttingen, Germany

Event date

Aug 12, 2024

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—