Dans cette thèse, je m’intéresse à deux extensions naturelles des automates finis (FA) : les automates finis bidirectionnels (2FA) qui reconnaissent des langages et les transducteur bidirectionnels (2T) qui calculent des relations binaires sur les mots.

Les 2FA sont calculatoirement équivalents aux FA même dans leur version nondéterministe (2NFA). Cependant, dans le domaine de la complexité descriptionnelle, certaines questions demeurent. Posée en 1978 par Sakoda et Sipser, la question du coût de la simulation d’un 2NFA par un 2DFA (D pour déterministe) est encore ouverte. Dans cette thèse je traite cette question dans un cas restreints, où les choix non-déterministes effectués par le 2NFA ne peuvent avoir lieu qu’au bords du mots d’entrée (2ONFA). Je montre que la simulation d’un 2ONFA par un 2DFA est sous-exponentielle (mais super-polynômiale). Sous l’hypothèse L=NL, cette conversion devient polynômial. De plus, je montre que la complémentation, et la simulation par un 2ONFA haltant (c’est à dire sans calcul infini) est polynômiale. Enfin, je considère également le cas des automates alternants pour lesquels des résultats similaires peuvent être obtenus.

Les transducteurs classiques (unidirectionnels) sont bien connus, et jouissent de caractérisations fortes (relations rationnelles, logique). Cependant, leur version bidirectionnelle (2T) est assez méconnue, spécialement dans le cas nondéterministe. Dans ce domaine, ma thèse apporte une contribution nouvelle : une caractérisation algébrique des relations acceptées lorsque les alphabets d’entrée et de sortie sont unaires. Celle-ci peut s’exprimer différemment : les 2T unaires sont équivalents au 2T boustrophédons (où les changements de direction de la tête de lecture ne peuvent intervenir qu’au bord du mot d’entrée). Je montre également que les hypothèses fortes faites sur les alphabets sont nécessaires.

Ceci nous mène finalement à l’étude générale des relations binaires sur les mots. On s’interesse alors à la composition de relations, qui nous permet de considérer leur cloture transitive. Si dans la plupart des cas, la cloture transitive d’une relation rationnelle est un ensemble non-récursif, on montre que la situation est différente lorsque la relation préserve la longeur, ou losque les alphabets sont unaires et que la relation est synchrone.

This PhD is about two natural extensions of Finite Automata: the 2-way FA (2FA) and the 2-way transducers (2T).

The 2FA are computably equivalent to FA, even in their nondeterministic (2NFA) variant. However, in the Descriptional Complexity area, some questions remain. Raised by Sakoda and Sipser in 1978, the question of the cost of the simulation of 2NFA by 2DFA is still open. In this manuscript I give an answer in a restricted case in which the nondeterministic choices of the 2NFA may occur at the border of the input only (2ONFA). I show that every 2ONFA can be simulated by a 2DFA of subexponential (but superpolynomial) size. Under the assumptions L=NL, this cost is reduced to the polynomial level. Moreover, I prove that the complementation, and the simulation by a halting 2ONFA is polynomial.

Classical transducers (1-way) are well-known and admit nice characterizations (rational relations, logic). But their 2-way variant (2T) is still unknown, especially the nondeterministic case. In this area, my manuscript gives a new contribution: a algebraic characterization of the relations accepted by 2NT when both the input and output alphabets are unary. It can be reformulated as follows: each unary 2NT is equivalent to a sweeping (and even rotating) 2T. I also show that the assumptions made on the size of the alphabets are required.

The study of word relations, as algebraic object, and their transitive closure is another subject considered in my phd. When the relation belongs to some low level class, we are able to set the complexity of its transitive closure. This quickly becomes uncomputable when higher classes are considered.