LR(0) conjunctive grammars and deterministic synchronized alternating pushdown automata

DOI10.1016/J.JCSS.2016.05.008MaRDI QIDQ736618zbMATH OpenOpenAlexFDO

Authors Tamar Aizikowitz, Michael Kaminski

Publication date 4 August 2016

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2016.05.008

zbMATH Keywords

conjunctive grammarsdeterministic synchronized alternating pushdown automataLR(0) conjunctive grammarssynchronized alternating pushdown automata

Mathematics Subject Classification ID

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

Recommendations

• \(LR(0)\) conjunctive grammars and deterministic synchronized alternating pushdown automata
• Linear conjunctive grammars and one-turn synchronized alternating pushdown automata
• Linear conjunctive grammars and one-turn synchronized alternating pushdown automata
• LR parsing for conjunctive grammars
• Top-down parsing of conjunctive languages

Cites work

• scientific article; zbMATH DE number 1747449 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• A recognition and parsing algorithm for arbitrary conjunctive grammars.
• Alternating Pushdown and Stack Automata
• Alternation
• Boolean grammars
• Conjunctive Grammars and Alternating Pushdown Automata
• Conjunctive and Boolean grammars: the true general case of the context-free grammars
• Conjunctive grammars and alternating pushdown automata
• Fast parsing for Boolean grammars: a generalization of Valiant's algorithm
• General context-free recognition in less than cubic time
• LR parsing for conjunctive grammars
• Nondeterminism and Boolean operations in pda's
• On the translation of languages from left to right
• Optimization of LR(k) parsers
• Recognition and parsing of context-free languages in time n3
• Syntax-Directed Transduction
• Top-down parsing of conjunctive languages
• Weak alternating automata are not that weak

Cited in

(6)

• Linear conjunctive grammars and one-turn synchronized alternating pushdown automata
• \(LR(0)\) conjunctive grammars and deterministic synchronized alternating pushdown automata
• Linear conjunctive grammars and one-turn synchronized alternating pushdown automata
• Unambiguous conjunctive grammars over a one-symbol alphabet
• Linear-space recognition for grammars with contexts
• Hardest languages for conjunctive and Boolean grammars

This page was built for publication: LR(0) conjunctive grammars and deterministic synchronized alternating pushdown automata

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