[Up]
Automata, semigroups and recognizability of words on ordinals
Abstract
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.
References
Download
Gzipped Postscript file (82Ko)