[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)

Valid HTML 4.01!



My email address 24 January 2015 22:04:40