Unsafe order-2 tree languages are context-sensitive

DOI10.1007/978-3-642-54830-7_10MaRDI QIDQ5410670zbMATH OpenOpenAlexFDO

Authors Naoki Kobayashi, Kazuhiro Inaba, Takeshi Tsukada

Publication date 16 April 2014

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-54830-7_10

Mathematics Subject Classification ID

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

Recommendations

• On word and frontier languages of unsafe higher-order grammars
• Automata, Languages and Programming
• Foundations of Software Science and Computational Structures
• Second-Order Simple Grammars
• Pumping Lemma for Higher-order Languages

Cited in

(5)

• Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity
• On word and frontier languages of unsafe higher-order grammars
• Intersection types for unboundedness problems
• The Complexity of the Diagonal Problem for Recursion Schemes
• Foundations of Software Science and Computational Structures

This page was built for publication: Unsafe order-2 tree languages are context-sensitive

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