• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 1
  • Tagged with
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

Combinatorial remarks on two-dimensional Languages

De Carli, Francesca 10 March 2009 (has links) (PDF)
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.

Page generated in 0.1048 seconds