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

Résumé en langue originale

Une figure 2D constituée de segments unitaires horizontaux et verticaux peut être représentée par une séquence de symboles, chacun d'entre eux engendrant un déplacement unitaire dans l'une des quatre directions: droite, gauche, haut ou bas. L'ensemble de ces symboles est noté P. Ainsi, à tout mot de P* est associée une unique figure inscrite dans le plan cartésien. Nous étudions différents systèmes de réécriture définis sur P* et conservant certaines propriétés des figures associées. D'abord, l'alphabet P contient quatre lettres engendrant des déplacements visibles (crayon baissé). Nous étudions deux systèmes de réécriture S et Sr-red conservant les figures: l'un d'entre eux permet d'obtenir tous les mots décrivant la même figure, l'autre est un système confluent fournissant un unique mot irréductible. Puis, nous complétons cet alphabet avec quatre lettres blanches engendrant des déplacements invisibles (crayon levé). Nous définissons un nouveau système de réécriture S' permettant d'obtenir exactement tous les mots décrivant la même figure qu'un mot initial. Pour chacun de ces deux alphabets, nous recherchons un parcours minimal décrivant une figure connexe donnée. Enfin, nous terminons par des résultats de décidabilité relatifs aux langages de mots de figure. Etant donné un langage rationnel inclus dans P*, nous pouvons décider si celui-ci contient des mots de contour de polyominos particuliers. Ces résultats sont établis à l'aide de deux systèmes de réécriture laissant invariantes certaines propriétés des mots de figure