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

DOI10.1007/978-3-642-02737-6_8zbMath1247.68125OpenAlexW2137124862MaRDI QIDQ3637217

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) Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Related Items (2)

Epsilon-reducible context-free languages and characterizations of indexed languages ⋮ Monoid-Based Approach to the Inclusion Problem on Superdeterministic Pushdown Automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• On the equivalence and containment problems for context-free languages
• A characterization of parenthesis languages

This page was built for publication: The Inclusion Problem of Context-Free Languages: Some Tractable Cases