Weak Büchi automaton
In computer science and automata theory, 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 such that for all pair of states and belonging to the same strongly connected component, is accepting if and only if is accepting.
A Büchi automaton accepts a word if there exists a run, such that at least one state occurring infinitely often in the final state set. 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 .The languages accepted by Weak Büchi automata are closed under union and intersection but not under complementation. For example, can be recognised by a Weak Büchi automaton but its complement cannot.
Non-deterministic Weak Büchi automata are more expressive than Weak Büchi automata. As an example, the language can be decided by a Weak Büchi automaton but by no deterministic Büchi automaton.