Alternating Finite Automaton

Get Alternating Finite Automaton essential facts below. View Videos or join the Alternating Finite Automaton discussion. Add Alternating Finite Automaton to your PopFlock.com topic list for future reference or share this resource on social media.
## Formal definition

## State complexity

## Computational complexity

## References

This article uses material from the Wikipedia page available here. It is released under the Creative Commons Attribution-Share-Alike License 3.0.

Alternating Finite Automaton

In automata theory, an **alternating finite automaton** (**AFA**) is a nondeterministic finite automaton whose transitions are divided into *existential* and *universal* transitions. For example, let *A* be an alternating automaton.

- For an existential transition ,
*A*nondeterministically chooses to switch the state to either or , reading*a*. Thus, behaving like a regular nondeterministic finite automaton. - For a universal transition ,
*A*moves to**and**, 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 languages.

An alternative model which is frequently used is the one where Boolean combinations are represented as *clauses*. For instance, one could assume the combinations to be in disjunctive normal form so that would represent . The state **tt** (*true*) is represented by in this case and **ff** (*false*) by .
This clause representation is usually more efficient.

An alternating finite automaton (AFA) is a 6-tuple, , where

- is a finite set of existential states. Also commonly represented as .
- is a finite set of universal states. Also commonly represented as .
- is a finite set of input symbols.
- is a set of transition relations to next state .
- is the initial (start) state, such that .
- is a set of accepting (final) states such that .

The model was introduced by Chandra, Kozen and Stockmeyer.^{[1]}

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

Chandra et al.^{[1]} proved that converting an -state AFA to an equivalent DFA
requires states in the worst case. Another construction by Fellah, Jürgensen and Yu.^{[2]} converts an AFA with states to a nondeterministic finite automaton (NFA) with up to states by performing a similar kind of powerset construction as used for the transformation of an NFA to a DFA.

The membership problem asks, given an AFA and a word , whether accepts . This problem is P-complete.^{[3]} 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^{[3]}.

- ^
^{a}^{b}Chandra, Ashok K.; Kozen, Dexter C.; Stockmeyer, Larry J. (1981). "Alternation".*Journal of the ACM*.**28**(1): 114-133. doi:10.1145/322234.322243. ISSN 0004-5411. **^**Fellah, A.; Jürgensen, H.; Yu, S. (1990). "Constructions for alternating finite automata*".*International Journal of Computer Mathematics*.**35**(1-4): 117-132. doi:10.1080/00207169008803893. ISSN 0020-7160.- ^
^{a}^{b}Theorem 19 of Holzer, Markus; Kutrib, Martin (2011-03-01). "Descriptional and computational complexity of finite automata--A survey".*Information and Computation*.**209**(3): 456-470. doi:10.1016/j.ic.2010.11.013. ISSN 0890-5401.

- Pippenger, Nicholas (1997).
*Theories of Computability*. Cambridge University Press. ISBN 978-0-521-55380-3.

This article uses material from the Wikipedia page available here. It is released under the Creative Commons Attribution-Share-Alike License 3.0.

Popular Products

Music Scenes

Popular Artists