Conjunctive grammars and alternating pushdown automata

DOI10.1007/s00236-013-0177-3zbMath1358.68155OpenAlexW2025957242MaRDI QIDQ2377302

Tamar Aizikowitz, Michael Kaminski

Publication date: 28 June 2013

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00236-013-0177-3

Mathematics Subject Classification ID

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

Related Items

LINEAR CONJUNCTIVE GRAMMARS AND ONE-TURN SYNCHRONIZED ALTERNATING PUSHDOWN AUTOMATA ⋮ Conjunctive and Boolean grammars: the true general case of the context-free grammars ⋮ LR(0) conjunctive grammars and deterministic synchronized alternating pushdown automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Conjunctive grammars with restricted disjunction
• Nondeterminism and Boolean operations in pda's
• A recognition and parsing algorithm for arbitrary conjunctive grammars.
• Top-down parsing of conjunctive languages
• Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth
• Linear Conjunctive Grammars and One-Turn Synchronized Alternating Pushdown Automata
• LR(0) Conjunctive Grammars and Deterministic Synchronized Alternating Pushdown Automata
• BOOLEAN GRAMMARS AND GSM MAPPINGS
• Alternating Pushdown and Stack Automata
• Conjunctive Grammars and Alternating Pushdown Automata
• CONJUNCTIVE GRAMMARS GENERATE NON-REGULAR UNARY LANGUAGES
• Weak alternating automata are not that weak
• Visibly pushdown languages
• Systolic trellis automatata †
• Alternation
• On the equivalence of linear conjunctive grammars and trellis automata
• Finite-Turn Pushdown Automata
• On the translation of languages from left to right
• EFFICIENT AUTOMATON-BASED RECOGNITION FOR LINEAR CONJUNCTIVE LANGUAGES

This page was built for publication: Conjunctive grammars and alternating pushdown automata