Editing Alternating finite automaton

In [[automata theory]], an '''alternating finite automaton''' ('''AFA''') is a [[nondeterministic finite automaton]] whose transitions are divided into ''[[existential quantification|existential]]'' and ''[[universal quantification|universal]]'' transitions. For example, let ''A'' be an alternating [[automaton]].
* For an existential transition <math>(q, a, q_1 \vee q_2)</math>, ''A'' nondeterministically chooses to switch the state to either <math>q_1</math> or <math>q_2</math>, reading ''a''. Thus, behaving like a regular [[nondeterministic finite automaton]].
* For a universal transition <math>(q, a, q_1 \wedge q_2)</math>, ''A'' moves to <math>q_1</math> '''and''' <math>q_2</math>, reading ''a'', simulating the behavior of a parallel machine.

Note that due to the universal quantification a run is represented by a run ''tree''. ''A'' accepts a word ''w'', if there ''exists'' a run tree on ''w'' such that ''every'' path ends in an accepting state.

A basic theorem states that any AFA is equivalent to a [[deterministic finite automaton]] (DFA), hence AFAs accept exactly the [[regular language]]s.

An alternative model which is frequently used is the one where Boolean combinations are in [[disjunctive normal form]] so that, e.g., <math>\{\{q_1\},\{q_2,q_3\}\}</math> would represent <math>q_1 \vee (q_2 \wedge q_3)</math>. The state '''tt''' (''true'') is represented by <math>\{\emptyset\}</math> in this case and '''ff''' (''false'') by <math>\emptyset</math>. This representation is usually more efficient.

Alternating finite automata can be extended to accept trees in the same way as [[tree automaton|tree automata]], yielding [[alternating tree automaton|alternating tree automata]].

==Formal definition==
An alternating finite automaton (AFA) is a [[n-tuple|5-tuple]],
<math>(Q, \Sigma, q_0, F, \delta)</math>, where

*<math>Q</math> is a finite set of states;
*<math>\Sigma</math> is a finite set of input symbols;
*<math>q_0\in Q</math> is the initial (start) state;
*<math>F\subseteq Q</math> is a set of accepting (final) states;
*<math>\delta\colon Q\times\Sigma\times\{0,1\}^Q\to\{0,1\}</math> is the transition function.

For each string <math>w\in\Sigma^*</math>, we define the acceptance function <math>A_w\colon Q\to\{0,1\}</math> by induction on the length of <math>w</math>:

*<math>A_\epsilon(q)=1</math> if <math>q\in F</math>, and <math>A_\epsilon(q)=0</math> otherwise;
*<math>A_{aw}(q)=\delta(q,a,A_w)</math>.

The automaton accepts a string <math>w\in\Sigma^*</math> if and only if <math>A_w(q_0)=1</math>.

This 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>

==State complexity==
{{main article|State complexity}}

Even though AFA can accept exactly the [[regular language]]s, they are different from other types of finite automata in the succinctness of description, measured by the number of their states.

Chandra et al.<ref name="ChandraKozen1981" /> proved that converting an <math>n</math>-state AFA to an equivalent DFA
requires <math>2^{2^n}</math> states in the worst case, though a DFA for the reverse language can be constructued with only <math>2^n</math> states. Another construction by Fellah, Jürgensen and Yu.<ref name="FellahJürgensen1990">{{cite journal|last1=Fellah|first1=A.|last2=Jürgensen|first2=H.|last3=Yu|first3=S.|title=Constructions for alternating finite automata∗|journal=International Journal of Computer Mathematics|volume=35|issue=1–4|year=1990|pages=117–132|issn=0020-7160|doi=10.1080/00207169008803893}}</ref> converts an AFA with <math>n</math> states to a [[nondeterministic finite automaton]] (NFA) with up to <math>2^n</math> states by performing a similar kind of powerset construction as used for the transformation of an NFA to a DFA.

==Computational complexity==

The membership problem asks, given an AFA <math>A</math> and a [[word (formal languages)|word]] <math>w</math>, whether <math>A</math> accepts <math>w</math>. This problem is [[P-complete]].<ref name="holzer2010descriptional">Theorem 19 of {{Cite journal|date=2011-03-01|title=Descriptional and computational complexity of finite automata—A survey|journal=Information and Computation|language=en|volume=209|issue=3|pages=456–470|doi=10.1016/j.ic.2010.11.013|issn=0890-5401|last1=Holzer|first1=Markus|last2=Kutrib|first2=Martin|doi-access=}}</ref> This is true even on a singleton alphabet, i.e., when the automaton accepts a [[unary language]].

The non-emptiness problem (is the language of an input AFA non-empty?), the universality problem (is the complement of the language of an input AFA empty?), and the equivalence problem (do two input AFAs recognize the same language) are [[PSPACE-complete]] for AFAs{{r|holzer2010descriptional|pages=Theorems 23, 24, 25}}.

==References==
{{reflist}}
* {{cite book | title=Theories of Computability | first=Nicholas | last=Pippenger | authorlink=Nick Pippenger | publisher=[[Cambridge University Press]] | year=1997 | isbn=978-0-521-55380-3 }}

{{DEFAULTSORT:Alternating Finite Automaton}}
[[Category:Finite-state machines]]