A recognition and parsing algorithm for arbitrary conjunctive grammars.

DOI10.1016/S0304-3975(02)00853-8MaRDI QIDQ1401337zbMATH OpenFDO

Authors Alexander Okhotin

Publication date 17 August 2003

Published in Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

ComplexityParsingRecognitionConjunctive grammars

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Recommendations

• scientific article; zbMATH DE number 1747449
• On the closure properties of linear conjunctive languages.
• LR parsing for conjunctive grammars
• scientific article; zbMATH DE number 2155200
• Conjunctive and Boolean grammars: the true general case of the context-free grammars

Cites work

• scientific article; zbMATH DE number 3555903 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• scientific article; zbMATH DE number 1962782 (Why is no real title available?)
• scientific article; zbMATH DE number 1747449 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• A Note on Tape-Bounded Complexity Classes and Linear Context-Free languages
• An Improved Context-Free Recognizer
• An efficient context-free parsing algorithm
• Space-bounded reducibility among combinatorial problems
• Top-down parsing of conjunctive languages

Cited in

(20)

• On the number of nonterminals in linear conjunctive grammars
• Improved normal form for grammars with one-sided contexts
• One-nonterminal conjunctive grammars over a unary alphabet
• EFFICIENT AUTOMATON-BASED RECOGNITION FOR LINEAR CONJUNCTIVE LANGUAGES
• The hardest linear conjunctive language
• Top-down parsing of conjunctive languages
• \(LR(0)\) conjunctive grammars and deterministic synchronized alternating pushdown automata
• scientific article; zbMATH DE number 1747449 (Why is no real title available?)
• LR parsing for conjunctive grammars
• On the closure properties of linear conjunctive languages.
• Conjunctive and Boolean grammars: the true general case of the context-free grammars
• Complexity of equations over sets of natural numbers
• scientific article; zbMATH DE number 1962778 (Why is no real title available?)
• Linear conjunctive grammars and one-turn synchronized alternating pushdown automata
• Path querying with conjunctive grammars by matrix multiplication
• Conjunctive grammars and alternating pushdown automata
• scientific article; zbMATH DE number 2155200 (Why is no real title available?)
• LR(0) conjunctive grammars and deterministic synchronized alternating pushdown automata
• Recognizing two-sided contexts in cubic time
• scientific article; zbMATH DE number 1962782 (Why is no real title available?)

This page was built for publication: A recognition and parsing algorithm for arbitrary conjunctive grammars.

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