Automata, Semigroups and Recognizability of Words on Ordinals

Nicolas Bédon

International Journal of Algebra and Computation · 1998 · 23 citations · 5 references

Concepts

Abstract

For a given integer n, we define ω n -semigroups as a generalization of ω-semigroups for languages of words of length less than ω n+1 . 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 as free as the Kleene closure operator is. Naturally, the notion of syntactic congruence still works on ω n -semigroups: among all ω n -semigroups recognizing a regular language X, there exists an unique ω n -semigroup of which all others are refinements.

References

5