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

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

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

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 (1)

• APPROXIMATING DEPENDENCY GRAMMARS THROUGH INTERSECTION OF STAR-FREE REGULAR LANGUAGES

   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 👍 👎
• Title not available (Why is that?) 👍 👎
• Finite generation of ambiguity in context-free languages 👍 👎
• Title not available (Why is that?) 👍 👎

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)