Tree generating context-free grammars and regular tree grammars are equivalent

Kószó, Dávid (2022) Tree generating context-free grammars and regular tree grammars are equivalent Annales Mathematicae et Informaticae. 56. pp. 58-70. ISSN 1787-6117 (Online)

[thumbnail of AMI_56_from58to70.pdf] pdf
AMI_56_from58to70.pdf

Download (549kB) [error in script]
Hivatalos webcím (URL): https://doi.org/10.33039/ami.2022.12.007

Absztrakt (kivonat)

We show that it is decidable whether the language generated by a given context-free grammar over a tree alphabet is a tree language. Furthermore, if the answer to this question is “yes”, then we can even effectively construct a regular tree grammar which generates that tree language.

Mű típusa: Folyóiratcikk - Journal article
Szerző:
Szerző neve
Email
MTMT azonosító
ORCID azonosító
Közreműködés
Kószó, Dávid
NEM RÉSZLETEZETT
NEM RÉSZLETEZETT
NEM RÉSZLETEZETT
Szerző
Kapcsolódó URL-ek:
Kulcsszavak: context-free grammar, regular tree grammar, tree language, parenthesis grammar, tree generating context-free grammar, decidability
Nyelv: angol
Kötetszám: 56.
DOI azonosító: 10.33039/ami.2022.12.007
ISSN: 1787-6117 (Online)
Felhasználó: Tibor Gál
Dátum: 30 Dec 2022 17:17
Utolsó módosítás: 30 Dec 2022 17:17
URI: http://publikacio.uni-eszterhazy.hu/id/eprint/7587
Műveletek (bejelentkezés szükséges)
Tétel nézet Tétel nézet