The Hausdorff-Kuratowski hierarchy of \(\omega\)-regular languages and a hierarchy of Muller automata (Q1184990): Difference between revisions

Let \(\Sigma\) be a finite alphabet and \(\Sigma^ \omega\) the set of infinite strings over \(\Sigma\). The author gives a characterization of those \(G_ \delta\) subsets of \(\Sigma^ \omega\) which are deterministic \(\omega\)-regular (i.e., accepted by Büchi automata) and characterizes \(\omega\)-regular languages in terms of these rational \(G_ \delta\) sets. This characterization yields a hierarchy of \(\omega\)-regular languages that is similar to the difference hierarchy of Hausdorff and Kuratowski for \(\underset\sim\Delta_ 3^ 0\) sets. Both hierarchies coincide, when restricted to \(\omega\)-regular languages. These results yield an effective procedure for determining the complexity of a given Muller automaton.