Formal Definition
Formally, a deterministic Muller-automaton is a tuple A = (Q,Σ,δ,q0,F) that consists of the following information:
- Q is a finite set. The elements of Q are called the states of Q.
- Σ is a finite set called the alphabet of A.
- δ: Q × Σ → Q is a function, called the transition function of A.
- q0 is an element of Q, called the initial state.
- F is a set of sets of states. Formally, F ⊆ P(Q) where P(Q) is powerset of Q. F defines the acceptance condition. A accepts exactly those runs in which the set of infinitely often occurring states is an element of F
In a non-deterministic Muller automaton, the transition function δ is replaced with a transition relation Δ that returns a set of states and initial state is q0 is replaced by a set of initial states Q0. Generally, Muller automaton refers to non-deterministic Muller automaton.
For more comprehensive formalism look at ω-automaton.
Read more about this topic: Muller Automaton
Famous quotes containing the words formal and/or definition:
“The conviction that the best way to prepare children for a harsh, rapidly changing world is to introduce formal instruction at an early age is wrong. There is simply no evidence to support it, and considerable evidence against it. Starting children early academically has not worked in the past and is not working now.”
—David Elkind (20th century)
“It’s a rare parent who can see his or her child clearly and objectively. At a school board meeting I attended . . . the only definition of a gifted child on which everyone in the audience could agree was “mine.””
—Jane Adams (20th century)