Equivalence of infinite behavior of finite automata (Q1060562)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Equivalence of infinite behavior of finite automata |
scientific article |
Statements
Equivalence of infinite behavior of finite automata (English)
0 references
1984
0 references
Working on an infinite word, a deterministic finite automaton generates a sequence of passed states. We say that a given word is accepted by a given automaton iff the above sequence has infinitely many occurrences of some terminal state. That definition can be easily transferred to non- deterministic automata by adding ''there exists such a sequence of passed states that has...''. Two automata are said to be equivalent iff their sets of accepted words are equal. The well-known Büchi's algorithm for deciding, given two finite automata, upon their equivalence, requires a computational time proportional to \((n^ 2)^{n^ 2}\) where n is the maximal number of states of two given automata. Here a new algorithm is proposed which requires only \(n^ 32^{3n(n+1)}\).
0 references
deterministic automata
0 references
algorithm for deciding equivalence
0 references
time complexity
0 references
non-deterministic automata
0 references