Ma thèse de doctorat

Information sur ma thèse de doctorat, réalisé sous la direction de Christian Choffrut, au LIAFA, à l'université Paris VII où j'étais allocataire de recherche.

Version anglaise

Les pistes WORM (angl. «~write once, read many~») permettent d'étendre les bandes d'entrée de différents modèles d'automates bidirectionnels. Leur ajout aux automates finis bidirectionnels déterministes (2DFAs), non-déterministes (2NFAs) et déterministes avec galet (P-2DFAs) donne des modèles (WORM-2DFAs, WORM-2NFAs et P-WORM-2DFAs) aux langages réguliers, tandis que leur ajout aux automates alternants (2AFAs) ou non-déterministes munis d'un galet (P-2NFAs) donne des modèles pouvant reconnaître des langages non-réguliers. L'opération de collage d'un langage de mots ou d'images consiste à prendre des éléments de ce langage à les superposer à des positions arbitraires, de façon à former de nouveaux mots ou de nouvelles images. Cette opération peut être facilement réalisée par un WORM-2NFA. Le collage d'un langage régulier de mots est régulier, bien que son automaticité puisse être exponentiellement plus grande. Pour les images, le collage d'un langage reconnaissable n'est pas nécessairement reconnaissable, même lorsque le langage est réduit à deux éléments sur trois couleurs. Les pistes WORM ont été initialement introduites pour étendre les automates bidirectionnels déterministes à pile (2DPDAs) donnant les WORM-2DPDAs. Bien que ces deux modèles correspondent étroitement à la classe des langages reconnaissables en temps polynomial, leur puissance de calcul relative à nombre de têtes égal reste une question ouverte. Un langage de programmation structuré, compilable vers 2DPDAs et WORM-2DPDAs et appelé Diamond, permet d'explorer plus facilement les capacités respectives de ces modèles dans l'idée de trouver un langage les séparant, mais aussi pour la recherche de nouveaux algorithmes à temps d'exécution linéaires.

En anglais :

2005-12-10