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)
![[img]](http://publikacio.uni-eszterhazy.hu/style/images/fileicons/text.png) |
pdf
AMI_56_from58to70.pdf Download (549kB) |
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 | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| 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 |
 |
Tétel nézet |
