Conjunctive grammars and alternating pushdown automata

DOI10.1007/S00236-013-0177-3MaRDI QIDQ2377302zbMATH OpenOpenAlexFDO

Authors 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

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

Cites work

• LR(0) conjunctive grammars and deterministic synchronized alternating pushdown automata
• A recognition and parsing algorithm for arbitrary conjunctive grammars.
• Alternating Pushdown and Stack Automata
• Alternation
• Boolean grammars and gsm mappings
• Conjunctive Grammars and Alternating Pushdown Automata
• CONJUNCTIVE GRAMMARS GENERATE NON-REGULAR UNARY LANGUAGES
• Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth
• Conjunctive grammars with restricted disjunction
• EFFICIENT AUTOMATON-BASED RECOGNITION FOR LINEAR CONJUNCTIVE LANGUAGES
• Finite-Turn Pushdown Automata
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 1747449 (Why is no real title available?)
• scientific article; zbMATH DE number 1759456 (Why is no real title available?)
• scientific article; zbMATH DE number 1929959 (Why is no real title available?)
• Linear conjunctive grammars and one-turn synchronized alternating pushdown automata
• Nondeterminism and Boolean operations in pda's
• On the equivalence of linear conjunctive grammars and trellis automata
• On the translation of languages from left to right
• Systolic trellis automatata †
• Top-down parsing of conjunctive languages
• Visibly pushdown languages
• Weak alternating automata are not that weak

Cited in

(10)

• A grammatical characterization of alternating pushdown automata
• Linear conjunctive grammars and one-turn synchronized alternating pushdown automata
• BREADTH AND DEPTH GRAMMARS AND DEQUE AUTOMATA
• Conjunctive and Boolean grammars: the true general case of the context-free grammars
• Two Grammatical Equivalents of Flip-Pushdown Automata
• ON ALTERNATING PHRASE-STRUCTURE GRAMMARS
• On state-alternating context-free grammars
• Pushdown Automata and Context-Free Grammars in Bisimulation Semantics
• Context-free, conjunctive and Boolean grammars and SCYK automata
• LR(0) conjunctive grammars and deterministic synchronized alternating pushdown automata

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

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