The inclusion problem of context-free languages: some tractable cases
From MaRDI portal
Publication:3086239
DOI10.1142/S0129054111008040zbMATH Open1209.68293MaRDI QIDQ3086239FDOQ3086239
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)
Recommendations
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 (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
- 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)
