Finite-state \(\omega\)-languages (Q794443): Difference between revisions

This is an important paper about the basics of sets of infinite sequences of words, customarily referred to as \(\omega\)-languages. In particular, the paper is a contribution to the theory of finite-state \(\omega\)- languages introduced by \textit{B. A. Trakhtenbrot} [Sib. Math. Zh. 3, 103- 131 (1962; Zbl 0115.007)]. The paper under review discusses the problem to what extent the class of finite-state \(\omega\)-languages and the class of regular \(\omega\)-languages coincide. The earlier investigations along these lines [e.g., \textit{M. Linna}, Inf. Control 31, 272-293 (1976; Zbl 0329.68066)] have shown that the restriction of computational power is not successful to topological considerations, estimating the exact borderline in the Borel hierarchy between the ranges where all finite-state \(\omega\)-languages are regular and where not. To this end, some general properties of both regular and finite-state \(\omega\)-languages are established. As a by-result a partial solution to the minimization problem for finite automata accepting regular \(\omega\)-languages is obtained.