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 17876117
|
Text
AMI_56_from58to70.pdf - Published Version Download (549kB) | Preview |
Official URL: http://doi.org/10.33039/ami.2022.12.007
Abstract
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.
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | context-free grammar, regular tree grammar, tree language, parenthesis grammar, tree generating context-free grammar, decidability |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
| Depositing User: | Tibor Gál |
| Date Deposited: | 09 Jan 2023 09:37 |
| Last Modified: | 09 Jan 2023 09:37 |
| URI: | http://real.mtak.hu/id/eprint/156201 |
Actions (login required)
 |
Edit Item |
