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

DOI10.25596/JALC-2016-203zbMATH Open1376.68082OpenAlexW2579834381MaRDI QIDQ5267521FDOQ5267521

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

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

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)

Cited In (8)

• Regular Approximation of Weighted Linear Context-Free Tree Languages
• Title not available (Why is that?)
• An operational and denotational approach to non-context-freeness
• Self-embedded context-free grammars with regular counterparts
• Tree generating context-free grammars and regular tree grammars are equivalent
• Linearity and nondeletion on monadic context-free tree grammars
• Context-free tree grammars are as powerful as context-free jungle grammars
• Title not available (Why is that?)

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)