Combinatorial remarks on two-dimensional languages
Institution:
ChambéryDisciplines:
Directors:
Abstract EN:
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.
Abstract FR:
La thèse contient une première chapitre avec des préliminaires sur les langages bidimensionnels, nous donnons un bref examen des résultats principaux et des différentes caractérisations des langages reconnaissables par de système de Tiling System, qui jouent le rôle central dans la thèse. Alors nous décrivons la structure algébrique des familles des langages locales. Nous prouvons que cette structure est un treillis en ce qui concerne l'inclusion et nous étudions les propriétés du treillis. D'ailleurs nous traitons des problèmes informatiques, étudiant leur possibilité de décision et nous donnons la position, dans la hiérarchie arithmétique, des problèmes classiques sur des langages unidimensionnels maintenant tournées aux langues bidimensionnels. Dans la thèse après quelques définitions du basic au sujet de polyominoes, nous traitons le recognizability de plusieurs classes de polyominoes par des langues reconnaissables par de Tiling System. En particulier nous donnons les Tiling systèmes de pour des langues représentant quelques classes de polyominoes convex, comme H-convex ou parallélogramme. D'ailleurs nous étudions la recognizability de L-convex polyominoes. En conclusion, la pièce d'essai de la thèse est consacrée à l'application des langages reconnaissables par de Tiling systèmes au calcul d'ADN. Nous donnons l'idée au sujet de la construction avec de l'ADN de quelques classes de polyominoes (c. -à-d. La classe de parallélogramme polyominoes), obtenons à travers la famille des langues reconnaissables par de Tiling systèmes.