Editing Pushdown automaton (section)

==Alternating pushdown automata {{anchor|Alternating}}==
An '''alternating pushdown automaton''' (APDA) is a pushdown automaton with a state set

* <math>Q=Q_\exists \cup Q_\forall</math> where <math>Q_\exists \cap Q_\forall=\emptyset</math>.

States in <math>Q_\exists</math> and <math>Q_\forall</math> are called ''existential'' resp. ''universal''. In an existential state an APDA nondeterministically chooses the next state and accepts if ''at least one'' of the resulting computations accepts. In a universal state APDA moves to all next states and accepts if ''all'' the resulting computations accept.

The model was introduced by [[Ashok K. Chandra|Chandra]], [[Dexter Kozen|Kozen]] and [[Larry Stockmeyer|Stockmeyer]].<ref name="ChandraKozen1981">{{cite journal|last1=Chandra|first1=Ashok K.|last2=Kozen|first2=Dexter C.|last3=Stockmeyer|first3=Larry J.|title=Alternation|journal=Journal of the ACM|volume=28|issue=1|year=1981|pages=114–133|issn=0004-5411|doi=10.1145/322234.322243|doi-access=free}}</ref> [[Richard E. Ladner|Ladner]], [[Richard J. Lipton|Lipton]] and [[Larry Stockmeyer|Stockmeyer]]<ref name="LadnerLipton1984">{{cite journal|last1=Ladner|first1=Richard E.|last2=Lipton|first2=Richard J.|last3=Stockmeyer|first3=Larry J.|title=Alternating Pushdown and Stack Automata|journal=SIAM Journal on Computing|volume=13|issue=1|year=1984|pages=135–155|issn=0097-5397|doi=10.1137/0213010}}</ref> proved that this model is equivalent to [[EXPTIME]] i.e. a language is accepted by some APDA [[if, and only if]], it can be decided by an exponential-time algorithm.

Aizikowitz and Kaminski<ref name="AizikowitzKaminski2011">{{cite book|last1=Aizikowitz|first1=Tamar|title=Computer Science – Theory and Applications|last2=Kaminski|first2=Michael|chapter=LR(0) Conjunctive Grammars and Deterministic Synchronized Alternating Pushdown Automata|volume=6651|year=2011|pages=345–358|issn=0302-9743|doi=10.1007/978-3-642-20712-9_27|series=Lecture Notes in Computer Science|isbn=978-3-642-20711-2}}</ref> introduced ''synchronized alternating pushdown automata'' (SAPDA) that are equivalent to [[conjunctive grammar]]s in the same way as nondeterministic PDA are equivalent to context-free grammars.