Automata, semigroups and recognizability of words on ordinals


For a given integer n, we define ω^n semigroups as a generalization of ω-semigroups for languages of words of length less than ω^n. When they are finite, those algebraic structures define the same sets as those recognized by Choueka automata. These sets are also equivalent to regular expressions in which an unary operator standing for the infinite repetition of a language is free as the Kleene closure operator is. Naturally, the notion of syntactic congruence still works on ω^n-semigroups. Thus, given a recognizable language X, there exists an ω^n-semigroup smaller than the others recognizing X.



Gzipped Postscript file (82Ko)

Valid HTML 4.01!