computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includin ...

and

automata theory Automata theory is the study of abstract machines and automata, as well as the computational problems that can be solved using them. It is a theory in theoretical computer science. The word ''automata'' comes from the Greek word αὐτόματο� ...

, a Weak Büchi automaton is a formalism which represents a set of infinite words. A Weak Büchi automaton is a modification of

Büchi automaton In computer science and automata theory, a deterministic Büchi automaton is a theoretical machine which either accepts or rejects infinite inputs. Such a machine has a set of states and a transition function, which determines which state the machi ...

such that for all pair of states

q

and

q'

belonging to the same

strongly connected component In the mathematical theory of directed graphs, a graph is said to be strongly connected if every vertex is reachable from every other vertex. The strongly connected components of an arbitrary directed graph form a partition into subgraphs that ...

q

is accepting if and only if

q'

is accepting. A

accepts a word

w

if there exists a run, such that at least one state occurring infinitely often in the final state set

F

. For Weak Büchi automata, this condition is equivalent to the existence of a run which ultimately stays in the set of accepting states. Weak Büchi automata are strictly less-expressive than Büchi automata and than Co-Büchi automata.

Properties

The deterministic Weak Büchi automata can be minimized in time

O(n \log(n))

. The languages accepted by Weak Büchi automata are closed under union and intersection but not under complementation. For example,

(a+b)^*b^\omega

can be recognised by a Weak Büchi automaton but its complement

(b^*a)^\omega

cannot. Non-deterministic Weak Büchi automata are more expressive than Weak Büchi automata. As an example, the language

(a+b)^*b^\omega

can be decided by a Weak Büchi automaton but by no deterministic Büchi automaton.

References

* {{DEFAULTSORT:Weak Buchi automaton Automata (computation)