My PhD untitled "Automates sur les ordres linéaires : Complémentation" has been defended the 7th of december 2004.

The jury's members :

-Dominique Perrin, IGM, University of Marne-la-Vallée, France (President)

-Didier Caucal, CNRS, IRISA, Rennes, France (Referee)

-Jean-Eric Pin, LIAFA, University Paris 7, France (Referee)

-Jean Berstel, IGM, University de Marne-la-Vallée, France

-Véronique Bruyère, Université of Mons-Hainaut, Belgium

-Olivier Carton, LIAFA, Université Paris 7, France (Advisor)

PhD 's abstract

This thesis treats of rational sets of words indexed by linear orderings and particularly of the problem of the closure under complementation.

In a seminal paper of 1956, Kleene started the theory of languages establishing that automata on finite words and rational expressions have the same expressive power. Since then, this result has been extended to many structures such as infinite words (Büchi, Muller), bi-infinite words (Beauquier, Nivat, Perrin), ordinal words (Büchi, Bedon), traces, trees... . More recently, Bruyère and Carton have introduced automata accepting words indexed by linear orderings and the corresponding rational expressions. Those linear structures include infinite words, ordinal words and their mirrors. Kleene's theorem has been generalized to words indexed by countable scattered linear orderings, that is orderings without any sub-ordering isomorphic to Q.

For many structures, the class of rational sets forms a boolean algebra. This property is necessary to translate logic into automata. The closure under complementation was left as an open problem. In this thesis, we solve it in a positive way: we prove that the complement of a rational set of words indexed by scattered linear orderings is rational. The classical method to get an automaton accepting the complement of a rational set is trough determinization. We show that this method can not be applied in our case: An automaton is not necessary equivalent to a deterministic one. We have used other approaches. First, we generalize the proof of Büchi, based on congruence of words, to obtain the closure under complementation in the case of linear orderings of finite ranks. To get the whole result in the general case, we use the algebraic approach. We develop an algebraic structure extending the classical recognition by finite semigroups : semigroups are replaced by diamond-semigroups equipped with a generalized product. We prove that a set is rational iff it is recognized by a finite diamond-semigroup. We also prove that a canonical diamond-semigroup can be associated to each rational set : the syntactic diamond-semigroup. Our proof of the closure under complementation is effective.

The theorem of Schützenberger establishes that a set of finite words is star-free if and only if its syntatic semigroup is finite and aperiodic. To finish, we partially extend this result to linear orderings of finite ranks.

Manuscript to download

pdf version, gzipped pdf version , ps version , gzipped ps version.

Master

As for formal languages, an infinite graphs hierarchy exists. If vertices of graphs are coded by words and edges are defined by relations between vertices, each family of graphs is characterized by a type of relation. For instance, each label of a rational graph is defined by a rational relation, that is by a transducer. The traces of a graph (the path labels leading from and to finite sets of vertices) are a link between the infinite graph hierarchy and the chomsky hierarchy of formal languages. For instance, Morvan and Stirling have proved that the traces of rational graphs are exactly the context-sensitive languages. We have shown that this result stays true if we restrict to rational synchronized graphs defined by letter-to-letter transducers followed by rational relations.