THE INCLUSION PROBLEM OF CONTEXT-FREE LANGUAGES: SOME TRACTABLE CASES

DOI10.1142/S0129054111008040zbMath1209.68293MaRDI QIDQ3086239

Roberto Radicioni, Alberto Bertoni, Christian Choffrut

Publication date: 30 March 2011

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

rewrite systemsinclusion problemcompressed-equality problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Related Items (2)

Inclusion between the frontier language of a non-deterministic recursive program scheme and the Dyck language is undecidable ⋮ Visibly Pushdown Transducers with Well-Nested Outputs

Cites Work

• Homogeneous Thue systems and the Church-Rosser property
• String matching in Lempel-Ziv compressed strings
• Formal properties of XML grammars and languages
• Processing Compressed Texts: A Tractability Border
• Superdeterministic PDAs
• Word Problems and Membership Problems on Compressed Words
• A characterization of parenthesis languages

This page was built for publication: THE INCLUSION PROBLEM OF CONTEXT-FREE LANGUAGES: SOME TRACTABLE CASES