The language intersection problem for non-recursive context-free grammars

DOI10.1016/J.IC.2004.03.004zbMATH Open1069.68069OpenAlexW2024730357MaRDI QIDQ596298FDOQ596298

Authors: Mark-Jan Nederhof, Giorgio Satta 

Publication date: 10 August 2004

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2004.03.004

Recommendations

• On the complexity of intersecting regular, context-free, and tree languages
• Deciding the inequivalence of context-free grammars with 1-letter terminal alphapet is \(\sum ^ p_ 2\)-complete
• scientific article; zbMATH DE number 2086619
• Finite generation of ambiguity in context-free languages
• scientific article; zbMATH DE number 1747449

zbMATH Keywords

Computational complexityContext-free grammarsFormal languagesParsing algorithms

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Cites Work

• Title not available (Why is that?)
• On the Decidability of Grammar Problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Nondeterministic Space is Closed under Complementation
• Title not available (Why is that?)
• Title not available (Why is that?)
• Optimization of LR(k) parsers
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the equivalence, containment, and covering problems for the regular and context-free languages
• On the complexity analysis of static analyses
• Terminating Turing Machine Computations and the Complexity and/or decidability of Correspondence Problems, Grammars, and Program Schemes

Cited In (4)

• APPROXIMATING DEPENDENCY GRAMMARS THROUGH INTERSECTION OF STAR-FREE REGULAR LANGUAGES
• On the complexity of intersecting regular, context-free, and tree languages
• The emptiness of intersection problem for languages of \(k\)-valued categorial grammars (classical and Lambek) is undecidable
• A note on the emptiness of intersection problem for left Szilard languages

This page was built for publication: The language intersection problem for non-recursive context-free grammars

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