zbMATH — the first resource for mathematics

Deterministic and non ambiguous rational \(\omega\)-languages. (English) Zbl 0612.68073
Automata on infinite words, Ec. Printemps Inf. Théor., Le Mont Dore 1984, Lect. Notes Comput. Sci. 192, 18-27 (1985).
[For the entire collection see Zbl 0563.00019.]
It is known that not every rational \(\omega\)-language can be recognized by a deterministic automaton so that the class DRAT of deterministic rational \(\omega\)-languages is strictly included in the class RAT of all rational \(\omega\)-languages.
In this paper the notion of non-ambiguity is considered: an automaton (in the Büchi sense) recognizes a non-ambiguous language if every word of the language has only one successful computation. The author proves that every rational language is non-ambiguous.
In the first section the deterministic Muller automata are discussed. In the second one the topology on the set of infinite words is introduced and some of its properties are presented. In the third section the Landweber’s theorem is proved (Theorem III.1): ”If L is a language of RAT, then L is in DRAT iff L is a G-set” (i.e. sets which are countable intersections of open sets). In the last section the following result is proved (Theorem IV.1): ”Any rational \(\omega\)-language is non-ambiguous”.
Reviewer: G.Orman

68Q45 Formal languages and automata