The Inclusion Problem of Context-Free Languages: Some Tractable Cases

DOI10.1007/978-3-642-02737-6_8MaRDI QIDQ3637217zbMATH OpenOpenAlexFDO

Authors Roberto Radicioni, Alberto Bertoni, Christian Choffrut

Publication date 7 July 2009

Published in Developments in Language Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-02737-6_8

Mathematics Subject Classification ID

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

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
• scientific article; zbMATH DE number 1142316 (Why is no real title available?)
• scientific article; zbMATH DE number 1490000 (Why is no real title available?)
• scientific article; zbMATH DE number 1834672 (Why is no real title available?)
• On the equivalence and containment problems for context-free languages
• 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

(9)

• The inclusion problem for some subclasses of context-free languages
• Epsilon-reducible context-free languages and characterizations of indexed 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 intersection type system for deterministic pushdown automata
• The inclusion problem of context-free languages: some tractable cases
• An Efficient Algorithm for the Inclusion Problem of a Subclass of DPDAs
• scientific article; zbMATH DE number 7453188 (Why is no real title available?)
• The inherent ambiguity partial algorithm problem for 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 Q3637217)