La thèse contient un premier chapitre avec des préliminaires sur les langages bidimensionnels, sur les résultats principaux et sur les différentes caractérisations des langages reconnaissables par systèmes de pavages qui jouent un rôle central dans la thèse. Ensuite, nous décrivons la structure algébrique des familles des langages locaux. Nous prouvons que cette structure est un treillis par rapport à l'inclusion et nous étudions les propriétés de ce treillis. Par ailleurs, nous traitons des problèmes informatiques de décidabilité et nous donnons la position, dans la hiérarchie arithmétique, des problèmes classiques sur des langages de mots appliquées aux langages bidimensionnelles. Dans la thèse, après quelques définitions de base sur les polyominos, nous traitons la reconnaissabilité de plusieurs classes des polyominos par des langages reconnaissables par systèmes de pavages. En particulier, nous donnons les systèmes de pavages pour des langages représentant les classes des polyominos convexes, h-convexes ou parallélogrammes. Ensuite, nous étudions la reconnaissabilité des polyominos L-convexes. En conclusion, la dernière partie de la thèse est consacrée à l'application des langages reconnaissables par systèmes de pavages au calcul d'ADN. Nous donnons l'idée de la construction avec de l'ADN de quelques classes des polyominos (par exemple la classe des polyominos parallélogrammes) obtenues à travers la famille des langages reconnaissables par systèmes de pavages.
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00415871 |
| Date | 10 March 2009 |
| Creators | De Carli, Francesca |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | English |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.004 seconds