R-TRIVIAL LANGUAGES OF WORDS ON COUNTABLE ORDINALS

摘要

Following the recently proved variety theorem for transfinite words we give, in this paper, three instances of correspondence between varieties of finite ω_1-semigroups and varieties of ω_1-languages. We first characterize the class of languages which are recognized by automata in which overlapping limit transitions end in the same state. It turns out that the corresponding variety of ω_1 -semigroups is defined by an equation which has a topological interpretation in the case of infinite words. It characterizes languages of infinite words in the class Δ_2 = ∏_2 ∩ ∑_2 of the Borel hierarchy. This result is used to prove that an ω_1-language is recognized by an extensive automaton if and only if its syntactic ω_1 -semigroup is R-trivial and satisfies the Δ_2-equation. This result extends Eilenberg's result concerning R-trivial semigroups and extensive automata. We finally characterize ω_1 -languages recognized by extensive automata whose limit transitions are trivial.