It is known in the case of languages of finite words that the family of regular languages may be generated from any regular language by rational transductions. A regular language is characterized by a finite automaton that accepts strings in the language. This research paper addresses the analogous problem for &ohgr;-languages, that is, languages that include words of infinite length. A regular &ohgr;-language is characterized by a finite automaton satisfying either Büchi’s or Muller’s condition [1]. These conditions establish the terminal states, which appear infinitely often in a path determined by a word in the language.

It is known that the family Rat of regular &ohgr;-languages has at least one proper subfamily (Frat, the family of rational adherences) under &ohgr;-transduction. The &ohgr;-transductions are non-erasing morphisms--which map nonempty words to nonempty words, and therefore infinite words to infinite words--and their inverses. The authors show by appeal to known results on the topology of &ohgr;-languages that C-drat, the family of languages complementary to those recognized by a deterministic Büchi automaton, is likewise closed under &ohgr;-transduction. The paper establishes these as the complete set of such proper subfamilies.

The results shown depend on a characterization of  C-drat  as the family of &ohgr;-languages generated by the language a*b^&ohgr; in conjunction with two similar results for Rat and Frat shown in Latteaux and Timmerman [2]. The main lemmas show that any rational &ohgr;-language not in C-drat generates Rat, and any rational &ohgr;-language not in Frat generates C-drat. Since Frat is easily shown to have no proper subfamily, it follows that these three classes are the only closed subfamilies of Rat. A further consequence is that, given any two rational &ohgr;-languages, it can be determined whether one can be generated from the other. The results presented here provide a complete characterization of the rational &ohgr;-languages.