Université Lille1 - Sciences et Technologies Langages de mots de figures monoïdes inversifs et langages de mots à deux dimensions Picture word languages, inverse monoids and two-dimensional langagues 005.131 Monoïdes Langages formels Automates cellulaires Text Electronic Thesis or Dissertation fr 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. application/pdf 1 : 1 Mo https://pepite-depot.univ-lille.fr/LIBRE/Th_Num/1997/50376-1997-125.pdf Simplot David 1900-01-01 076987787 1997LIL10063 1997-01-01 Informatique Université Lille1 - Sciences et Technologies 026404184 Doctorat non oui ddc:000 ASCII PDF 9999