• Langue : Français
• Discipline : Informatique
• Identifiant : Inconnu
• Type de thèse : Doctorat
• Date de soutenance : 01/01/1997

Résumé en langue originale

L'objet de cette thèse est d'étudier à l'aide de la théorie des langages formels deux formalismes permettant de décrire des ensembles de figures ou images. Dans le premier cas, nous tentons de décrire des figures, objets à deux dimensions, à l'aide de mots, objets unidimensionnels - un mot correspond a un parcours de la figure. C'est ce que nous appelons les langages de mots de figures ; nous essayons d'exhiber des propriétés sur les ensembles de figures à partir de ce que l'on connaît sur les langages de mots qui les décrivent. Le deuxième formalisme découle de la démarche inverse: les figures sont des mots à deux dimensions et nous étendons des notions bien connues dans les mots, comme la reconnaissabilité, au cas à deux dimensions. Dans la première partie, nous donnons le moyen de représenter des ensembles finis de pixels connexes, qui forment un monoïde inversif, à l'aide d'un monoïde libre. Nous donnons un système de réécriture générique qui induit la congruence mettant en relation deux mots qui décrivent le même élément dans la représentation d'un monoïde inversif par un monoïde libre. Un mot représentant une figure, un langage de mots décrit un ensemble de figures. Nous montrons l'indécidabilité d'un certain nombre de propriétés existentielles - par exemple savoir s'il existe un mot décrivant un polyomino - dans un langage régulier. Dans la seconde partie, nous étudions les langages de mots à deux dimensions reconnaissables - obtenus par projection d'un langage local. Nous montrons que, contrairement à la définition, nous pouvons séparer les contrôles horizontaux et verticaux en introduisant la classe des langages de figures hv-locaux.