Non-self-embedding linear context-free tree grammars generate regular tree languages

DOI10.25596/JALC-2016-203MaRDI QIDQ5267521zbMATH OpenOpenAlexFDO

Authors Mark-Jan Nederhof, Markus Teichmann, Heiko Vogler

Publication date 13 June 2017

Full work available at URL https://research-repository.st-andrews.ac.uk/handle/10023/9995

zbMATH Keywords

context-free grammarself-embeddingregular tree grammarcontext-free tree grammar

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Recommendations

• Self-embedded context-free grammars with regular counterparts
• Linearity and nondeletion on monadic context-free tree grammars
• Generative capacity of subregularly tree controlled grammars
• The equivalence of tree adjoining grammars and monadic linear context-free tree grammars

Cited in

(8)

• An operational and denotational approach to non-context-freeness
• scientific article; zbMATH DE number 1523042 (Why is no real title available?)
• Context-free tree grammars are as powerful as context-free jungle grammars
• Tree generating context-free grammars and regular tree grammars are equivalent
• scientific article; zbMATH DE number 5251101 (Why is no real title available?)
• Regular Approximation of Weighted Linear Context-Free Tree Languages
• Self-embedded context-free grammars with regular counterparts
• Linearity and nondeletion on monadic context-free tree grammars

This page was built for publication: Non-self-embedding linear context-free tree grammars generate regular tree languages

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