In automata theory

Automata theory

In theoretical computer science, automata theory is the study of abstract machines and the computational problems that can be solved using these machines. These abstract machines are called automata...

, an alternating finite automaton (AFA) is a nondeterministic finite automaton whose transitions are divided into existential

Existential quantification

In predicate logic, an existential quantification is the predication of a property or relation to at least one member of the domain. It is denoted by the logical operator symbol ∃ , which is called the existential quantifier...

and universal

Universal quantification

In predicate logic, universal quantification formalizes the notion that something is true for everything, or every relevant thing....

transitions. For example, let A be an alternating automaton

Automaton

An automaton is a self-operating machine. The word is sometimes used to describe a robot, more specifically an autonomous robot. An alternative spelling, now obsolete, is automation.-Etymology:...

.

• 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 tells that any AFA is equivalent to an non-deterministic finite automaton (NFA) by performing a similar kind of powerset construction as it is used for the transformation of an NFA to a deterministic finite automaton (DFA). This construction converts an AFA with k states to an NFA with up to states.

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

Disjunctive normal form

In boolean logic, a disjunctive normal form is a standardization of a logical formula which is a disjunction of conjunctive clauses. As a normal form, it is useful in automated theorem proving. A logical formula is considered to be in DNF if and only if it is a disjunction of one or more...

 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.

Formal Definition

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 functions
  Function (mathematics)
  In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...
  
  to next state .
• is the initial (start) state, such that .
• is a set of accepting (final) states such that .