The inclusion problem of context-free languages: some tractable cases

DOI10.1142/S0129054111008040zbMATH Open1209.68293MaRDI QIDQ3086239FDOQ3086239

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)

Recommendations

• The Inclusion Problem of Context-Free Languages: Some Tractable Cases
• The inclusion problem for some subclasses of context-free languages
• scientific article
• scientific article; zbMATH DE number 4047162
• scientific article; zbMATH DE number 512829

zbMATH Keywords

inclusion problemrewrite systemscompressed-equality problem

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (8)

• Developments in Language Theory
• An Efficient Algorithm for the Inclusion Problem of a Subclass of DPDAs
• The inherent ambiguity partial algorithm problem for context free languages
• 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
• An efficient automata approach to some problems on context-free grammars.
• The Inclusion Problem of Context-Free Languages: Some Tractable Cases
• The inclusion problem for some subclasses of context-free languages

This page was built for publication: The inclusion problem of context-free languages: some tractable cases

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