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

DOI10.1016/j.jcss.2016.05.008zbMath1348.68079OpenAlexW2426482043MaRDI QIDQ736618

Michael Kaminski, Tamar Aizikowitz

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)

Related Items (3)

Linear-space recognition for grammars with contexts ⋮ Hardest languages for conjunctive and Boolean grammars ⋮ Unambiguous conjunctive grammars over a one-symbol alphabet

Cites Work

• Unnamed Item
• Unnamed Item
• Conjunctive and Boolean grammars: the true general case of the context-free grammars
• General context-free recognition in less than cubic time
• Nondeterminism and Boolean operations in pda's
• A recognition and parsing algorithm for arbitrary conjunctive grammars.
• Top-down parsing of conjunctive languages
• LR parsing for conjunctive grammars
• Boolean grammars
• Conjunctive grammars and alternating pushdown automata
• Optimization of LR(k) parsers
• Alternating Pushdown and Stack Automata
• Conjunctive Grammars and Alternating Pushdown Automata
• Weak alternating automata are not that weak
• Fast Parsing for Boolean Grammars: A Generalization of Valiant’s Algorithm
• Alternation
• Recognition and parsing of context-free languages in time n3
• Syntax-Directed Transduction
• On the translation of languages from left to right

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