# Combinatorial remarks on two-dimensional Languages

1 DSMI - Department of Mathematics and Computer Science - Dipartimento di Scienze Matematiche e Informatiche -Roberto Magari-

Abstract : The thesis contains a first charter with preliminaries on two-dimensional languages, we give a brief review of the main results and the different characterizations of tiling system recognizable languages which play the central role in the thesis. Then we describe the algebraic structure of the families of local languages. We show that this structure is a lattice with respect to the inclusion and we investigate the properties of the lattice. Moreover we deal with computational problems, studying their decidability and we give the position, in the arithmetical hierarchy, of the classical problems on string languages now turned to two-dimensional languages. In the thesis after some basic definitions concerning polyominoes, we deal with the recognizability of several classes of polyominoes by tiling system recognizable languages. In particular we give the tiling systems for languages representing some classes of convex polyominoes, as the h-convex or parallelogram. Moreover we investigate the recognizability of L-convex polyominoes. Finally, the la test part of the thesis is devoted to the application of tiling system recognizable languages to DNA computation. We give the idea about the construction with DNA of some classes of polyominoes i.e. the class of parallelogram polyominoes, get through to the family of tiling system recognizable languages.

Résumé : 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.

Mots-clés : Langages à deux dimensions pavages

Author: Francesca De Carli -

Source: https://hal.archives-ouvertes.fr/