Linearity and nondeletion on monadic context-free tree grammars

DOI10.1016/J.IPL.2004.10.008MaRDI QIDQ835003zbMATH OpenOpenAlexFDO

Authors Akio Fujiyoshi

Publication date 27 August 2009

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2004.10.008

zbMATH Keywords

context-free tree grammarformal languagestree adjoining grammar

Mathematics Subject Classification ID

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

Recommendations

• The equivalence of tree adjoining grammars and monadic linear context-free tree grammars
• The equivalence of tree adjoining grammars and monadic linear context-free tree grammars
• Non-self-embedding linear context-free tree grammars generate regular tree languages
• The equivalence of four extensions of context-free grammars

Cites work

• scientific article; zbMATH DE number 1941335 (Why is no real title available?)
• Mappings and grammars on trees
• Spinal-formed context-free tree grammars
• TAL recognition in O(M(n^2)) time
• The equivalence of four extensions of context-free grammars
• Tree adjunct grammars
• Tree generating regular systems
• Tree-Adjoining Language Parsing in O(n^6 ) Time

Cited in

(7)

• Spinal-formed context-free tree grammars
• Restarting Tree Automata and Linear Context-Free Tree Languages
• The equivalence of tree adjoining grammars and monadic linear context-free tree grammars
• The equivalence of four extensions of context-free grammars
• The equivalence of tree adjoining grammars and monadic linear context-free tree grammars
• On Tree Substitution Grammars
• Non-self-embedding linear context-free tree grammars generate regular tree languages

This page was built for publication: Linearity and nondeletion on monadic context-free tree grammars

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