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

DOI10.1016/J.IC.2004.03.004MaRDI QIDQ596298zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

Computational complexityContext-free grammarsFormal languagesParsing algorithms

Mathematics Subject Classification ID

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

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

Cites work

• scientific article; zbMATH DE number 3727583 (Why is no real title available?)
• scientific article; zbMATH DE number 43583 (Why is no real title available?)
• scientific article; zbMATH DE number 193480 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• scientific article; zbMATH DE number 3428547 (Why is no real title available?)
• scientific article; zbMATH DE number 3254900 (Why is no real title available?)
• scientific article; zbMATH DE number 3302285 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• Nondeterministic Space is Closed under Complementation
• On the Decidability of Grammar Problems
• On the complexity analysis of static analyses
• On the equivalence, containment, and covering problems for the regular and context-free languages
• Optimization of LR(k) parsers
• 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)