Conception de modèles génériques pour les machines à états finis
Institution:
RouenDisciplines:
Directors:
Abstract EN:
The work presented in this thesis takes place in the scope of automata theory and connects with the creation of a finite state compiler, WFSC that allows the creation and the processing of symbol class multitape weighted automata with identity and non-identity. This model of finite state machine is obtained by extending the transition labeling of finite state automata. The first part is dedicated to that generalization. The aim is to increase the expressiveness, as well as the compactness of these machines. We introduce the notion of symbol classes and we give definitions for automata, transducers and multitape automata labeled with symbol classes. We introduce in addition the notion for equi-constrained relation that extend the identity and non-identity relations. The second part is a contribution to the algorithmic of finite state machines. At first time, we study a set of operations for weighted multitape automata like join, and the auto-intersection. Due to link with the Post correspondance problem, we describea class of n-ary rational relations for which the auto-intersection can be computed and we give the related algorithms. In second time, we present the construction of the follow automata of a rational expression through the ZPC structure. An implementation was made that allowed the comparison of our construction with respect to the classical one, showing its efficiency in practice. Finally, we describe the implementation of virtual finite state machine inside XFST, that apply the principle of lazy evaluation to finite state machine, and we describe how symbol class multitape weighted automata with identity are modeled in WFSC. A programming technique that improve the behavior of polymorphic classes in C+++, called bitwise virtuality, is described. We finish by describing some applications in order to demonstrate that both the compiler and the WFSC library are easy to use.
Abstract FR:
Les travaux de ce mémoire s'inscrivent dans le cadre de la théorie des automates et s'articulent autour de la création d'un compilateur de machines à états finis, WFSC, permettant la création et la manipulation d'automates pondérés multibandes à classes de symboles avec identité et non-identité. Ce modèle de machine à états finis est obtenu par généralisation de l'étiquetage des transitions des automates à états finis. La première partie est consacrée à cette généralisation de l'étiquetage. Le but est d'augmenter le pouvoir d'expression et l'efficacité de leur représentation. Nous introduisons la notion de classe de symboles, puis donnons des définitions d'automates, transducteurs, automates multibandes étiquetés par classe de symboles et la notion de relation équi-contrainte comme extension des relations d'identité et de non-identité. La seconde partie est une contribution à l'algorithmique des machines à états finis. Nous étudions d'abord un certain nombre d'opérations pour les machines multibandes pondérées, comme la jointure et l'auto-intersection. Comme il existe une relation avec le problème de la correspondance de Post, nous décrivons une classe de relations rationnelles n-aires pour laquelle l'auto-intersection peut être calculée et donnons les algorithmes correspondants. Ensuite, nous présentons l'étude de la construction de l'automate des follows d'une expression rationnelle à l'aide de la structure ZPC. Une implémentation permettant de comparer cette construction par rapport à la construction classique, a été réalisée. Dans la dernière partie, nous décrivons l'implémentation des machines à états finis virtuelles dans XFST, qui applique le principe de l'évaluation paresseuse aux automates, puis la modélisation des automates pondérés multibandes à classes de symboles avec identité et non-identité dans WFSC. Une technique de programmation améliorant le comportement des classes polymorphes en C++, la bitwise virtuality, est décrite. Enfin, nous terminons par la description de quelques applications afin de démontrer la souplesse d'utilisation à la fois du compilateur et de la bibliothèque WFSC.