thesis

Contribution à l’algorithmique des automates pondérés à une, deux ou plusieurs bandes

Defense date:

Jan. 1, 2005

Edit

Institution:

Rouen

Disciplines:

Computer sciences

Authors:

Directors:

Abstract EN:

This PhD thesis deals with the automata theory. A general study of similarity relations and the notion a cover automata are presented. We define merging relations and the notion of cover transducers. A reduction algorithm is exposed and tested. Weighted multi-tape automata are a generalisation of automata and transducers. We define the join and auto-intersection operations and we present the corresponding algorithms. As a consequence of the Post's Correspondence Problem there does not exist a general algorithm of auto-intersection. We define a class of weighted multi-tape automata in which it is possible to compute the auto-intersection. After a State of the Art of finite state machine compilers, we present XEROX's compilers, WFSC and XFST, through their specificities. We present the '?' symbol and extended-alphabet machines, then the notion of virtual networks in XFST. Several characteristics of the generic and modular design of WFSC are exposed. We study the worst-case complexity for the printing of all paths of an acyclic automaton. We describe the structure that maximizes the complexity, then we compute this complexity for a given number of states.

Abstract FR:

Les travaux présentés dans ce mémoire se situent dans le cadre de la théorie des automates. Une étude générale des relations de similarité et la notion d'automate couvrant sont présentés. On définit les relations de fusion ainsi que la notion de transducteur couvrant. Un algorithme de réduction est proposé et expérimenté. Les automates multi-bandes pondérés sont une généralisation des automates et transducteurs. On définit des opérations de jointure et d'auto-intersection et on présente les algorithmes correspondants. Une conséquence du Problème de Correspondance de Post est qu'il n'existe pas d'algorithme général d'auto-intersection. On définit alors une classe d'automates multi-bandes pondérés dans laquelle il est possible de calculer l'auto-intersection. Après un état de l'art des logiciels manipulant les machines d'état finis, on présente les compilateurs d'états finis de XEROX, WFSC et XFST, à travers leurs spécificités. On présente le symbole '?' et les machines à alphabet étendu, puis la notion de réseau virtuel dans XFST. Plusieurs caractéristiques de la conception générique et modulaire de WFSC sont exposées. On propose une étude de la complexité au pire des cas de l'impression de tous les chemins d'un automate acyclique. On décrit la structure qui maximise la complexité, et on calcule cette complexité pour un nombre d'états donné.