Complexité raffinée du problème d'intersection d'automates

Abstract

Le problème d'intersection d'automates consiste à vérifier si plusieurs automates finis déterministes acceptent un mot en commun. Celui-ci est connu PSPACE-complet (resp. NL-complet) lorsque le nombre d'automates n'est pas borné (resp. borné par une constante).

Dans ce mémoire, nous étudions la complexité du problème d'intersection d'automates pour plusieurs types de langages et d'automates tels les langages unaires, les automates à groupe (abélien), les langages commutatifs et les langages finis.

Nous considérons plus particulièrement le cas où chacun des automates possède au plus un ou deux états finaux. Ces restrictions permettent d'établir des liens avec certains problèmes algébriques et d'obtenir une classification intéressante de problèmes d'intersection d'automates à l'intérieur de la classe P. Nous terminons notre étude en considérant brièvement le cas où le nombre d'automates est fixé.

The automata non emptiness intersection problem is to determine whether several deterministic finite automata accept a word in common. It is known to be PSPACE-complete (resp. NL-complete) whenever the number of automata is not bounded (resp. bounded by a constant).

In this work, we study the complexity of the automata intersection problem for several types of languages and automata such as unary languages, (abelian) group automata, commutative languages and finite languages. We raise the issue of limiting the number of final states to at most two in the automata involved.

This way, we obtain relationships with some algebraic problems and an interesting classification of automata intersection problems inside the class P. Finally, we briefly consider the bounded version of the automata intersection problem.