Safety is not a restriction at level 2 for string languages

DOI10.1007/978-3-540-31982-5_31MaRDI QIDQ5705907zbMATH OpenOpenAlexFDO

Authors Klaus Aehlig, J. G. de Miranda, Chih-Hao Luke Ong

Publication date 10 November 2005

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

Full work available at URL https://doi.org/10.1007/b106850

Mathematics Subject Classification ID

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

Recommendations

• Unsafe order-2 tree languages are context-sensitive
• Automata, Languages and Programming
• On word and frontier languages of unsafe higher-order grammars
• Higher-order pushdown trees are easy
• Second-Order Simple Grammars

Cited in

(10)

• On first-order logic and CPDA graphs
• The IO and OI hierarchies revisited
• MIX is a 2-MCFL and the word problem in \(\mathbb{Z}^2\) is captured by the IO and the OI hierarchies
• Inclusion between the frontier language of a non-deterministic recursive program scheme and the Dyck language is undecidable
• Model-checking games for typed -calculi
• Krivine machines and higher-order schemes
• On word and frontier languages of unsafe higher-order grammars
• On the expressivity of linear recursion schemes
• Unsafe order-2 tree languages are context-sensitive
• Slice closures of indexed languages and word equations with counting constraints

This page was built for publication: Safety is not a restriction at level 2 for string languages

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