francais? Up

Recognizable languages of words indexed by ordinals

01/15/98

Keywords

Language, ordinal, automaton, semigroup, logic, variety of languages.

Jury

Abstract

This thesis treats of recognizable languages of words indexed by ordinals.

Several classes of automata recognizing such words have been introduced by Büchi. Those classes differ by the length of words recognized by automata. We use four of them: the class for words of length $\omega$,the one for words of length less than $\omega^{n+1}$, where n is an integer, the class for words of denumerable length and the one for words of any length. We also use the usual Kleene automata, on words of finite length. We give another proof of the equivalence of those different definitions of automata: by choosing an automaton in one class, one can construct an automaton of an other class such that the restrictions of languages accepted by both automata to the smallest domain of both classes are identical. We also give an unified presentation for the determinisation of each class of automata whose domain is words of length at most denumerable.

Finite semigroups are another formalism equivalent to automata to define sets of finite words. Perrin, Pin and Wilke have introduced algebraic structures adapted to the study of languages of words of length $\omega$.These structures are equivalent to automata when they are finite. We generalize the algebraic approach of the theory of recognizable languages of words of length $\omega$ to words of length less than $\omega^{n+1}$, and to words of denumerable length: we define two algebraic structures, called $\omega^n$-semigroups and $\omega_1$-semigroups, equivalent, when they are finite, to automata respectively on words of length less than $\omega^{n+1}$ and of denumerable length. As for the case of words of length $\omega$, a finite algebra can be canonically associated to any recognizable language. We define the Schützenberger and wreath products on $\omega_1$-semigroups. We also extend the Eilenberg theorem of variety to words of denumerable length.

Finally, we give another proof of Büchi's theorem which establishes the equivalence between languages recognized by automata and languages defined by sentences of monadic second order logic for words of denumerable length. We extend the Schützenberger's theorem of equivalence between star-free languages and languages recognized by aperiodic finite semigroups to words of length less than $\omega^{n+1}$, and McNaughton and Papert's theorem of equivalence between star-free languages and languages defined by sentences of first order logic of the linear ordering to words of any length.


The entire document

The slides of the talk of the thesis

Valid HTML 4.01!

My email address 25 January 2015 11:14:26