Stephan Barth, Representation of ω-regular Languages by Languages of Finite Words

Stephan Barth
Representation of ω-regular Languages by Languages of Finite Words

There are several automata models for ω-regular languages, languages of infinite words. In all well-known models (Büchi, Parity, Rabin, Strett, Muller) minimization is NP-hard.

There is a lesser known model for representing omega-regular languages that performs better on this operation: Finite automata storing a finite word for every ultimate periodic word. Minimization algorithms for DFA can directly be applied, leading to minimization in O(n log n).

I will present this model with its already known transformations from and to Büchi automata and introduce algorithms for performing the most relevant operations (and, or, complement, projection) directly on this model.