Systèmes de Head et applications à la bio-informatique - Université de Lorraine
Theses Year : 2004

Head systems and applications to bio-informatics

Systèmes de Head et applications à la bio-informatique

Abstract

This work is situated in the heart of a recent domain: (bio)molecular computing, which is a domain where biology and computer science meet. This domain investigates models of computing having biological inspiration. Head splicing systems, based on the splicing operation, as well as their extensions are one of the most important models of computing in this domain. We concentrated on the study of different extensions of Head systems by showing often optimal universality results with respect to main parameters of these systems what permitted us to establish several frontiers between decidability and undecidability for these extensions. Moreover, we found several common features of these systems and we designed a generic method that permits to prove easily equivalences with classical models of computing. We also considered membrane systems that are inspired by the structure and the functioning of a living cell. We were particularly interested in the combination of these models and Head systems: splicing membrane systems and we solved a number of open problems for these systems. This work manipulates fundamental notions of the theory of computing and of the molecular computing. It gives solutions to certain important open problems of the last domain and it poses at the same time several interesting questions.
Ce travail se situe au c?ur d'un domaine récent: les calculs (bio)moléculaires qui se place à la rencontre de la biologie et de l'informatique. La recherche dans ce domaine porte sur des modèles de calcul ayant une inspiration biologique.Les systèmes de Head, fondés sur l'opération de la recombinaison, ainsi que leurs extensions représentent des modèles de calcul parmi les plus importants du domaine. Nous nous sommes concentrés sur l'étude de différentes extensions des systèmes de Head en présentant souvent des résultats d'universalité optimaux par rapport aux paramètres principaux de ces systèmes ce qui a permis d'établir plusieurs frontières entre la décidabilité et l'indécidabilité pour ces extensions. De plus, nous avons trouvé certains traits communs de ces systèmes et nous avons conçu une méthode générique permettant de démontrer facilement des équivalences avec des modèles de calcul classiques. Nous avons aussi considéré les systèmes à membranes qui sont inspirés par la structure et le fonctionnement de la cellule vivante. Nous nous sommes particulièrement intéressés à la combinaison de ces modèles et les systèmes de Head: les systèmes à membranes avec recombinaison et nous avons résolu une série des problèmes ouverts pour ces systèmes. Ce travail manipule des notions fondamentales de la théorie de la calculabilité et du calcul moléculaire et donne des solutions à certains problèmes importants de ce dernier domaine en posant dans le même temps plusieurs questions intéressantes.
Fichier principal
Vignette du fichier
Verlan.Serghei.SMZ0404.pdf (7.09 Mo) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

tel-01750252 , version 1 (29-03-2018)

Identifiers

  • HAL Id : tel-01750252 , version 1

Cite

Serghei Verlan. Systèmes de Head et applications à la bio-informatique. Autre [cs.OH]. Université Paul Verlaine - Metz, 2004. Français. ⟨NNT : 2004METZ004S⟩. ⟨tel-01750252⟩
111 View
127 Download

Share

More