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

DOI10.1142/S0129054111008040MaRDI QIDQ3086239zbMATH OpenFDO

Authors 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

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)

Recommendations

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

Cites work

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

Cited in

(10)

• Developments in Language Theory
• An intersection type system for deterministic pushdown automata
• 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
• Monoid-based approach to the inclusion problem on superdeterministic pushdown automata
• An efficient automata approach to some problems on context-free grammars.
• Visibly pushdown transducers with well-nested outputs
• 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)