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

DOI10.33039/AMI.2022.12.007MaRDI QIDQ5886207zbMATH OpenOpenAlexFDO

Authors Dávid Kószó

Publication date 30 March 2023

Published in Annales Mathematicae et Informaticae (Search for Journal in Brave)

Full work available at URL https://doi.org/10.33039/ami.2022.12.007

zbMATH Keywords

context-free grammardecidabilityparenthesis grammarregular tree grammartree generating context-free grammartree language

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Non-self-embedding linear context-free tree grammars generate regular tree languages
• Context-free tree grammars are as powerful as context-free jungle grammars
• scientific article; zbMATH DE number 1504824
• Generative capacity of subregularly tree controlled grammars
• On the multiplicity equivalence problem for context-free grammars

Cited in

(1)

• The equivalence of tree adjoining grammars and monadic linear context-free tree grammars

This page was built for publication: Tree generating context-free grammars and regular tree grammars are equivalent

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5886207)