Soutenance de thèse de Tarek KHALED

La programmation par ensemble réponse (Answer Set Programming, ASP) est un paradigme de programmation déclaratif basé sur la sémantique des modèles stables. L'idée derrière l'ASP est de coder un problème de calcul sous forme d'un ensemble de règles logiques, les modèles stables du programme logique correspondent aux solutions du problème de calcul initial. La grande expressivité de l'ASP, combinée au nombre croissant d'applications, a fait de l'implémentation de solveurs ASP un sujet de recherche important. Dans la première partie de la thèse, nous exploitons une nouvelle sémantique pour les programmes logiques dans la conception d'un nouveau système ASP. La sémantique nous donne la possibilité de calculer tous les modèles stables d'un programme logique, et de calculer des extra-modèles lorsque le programme logique n'a pas de modèles stables. La méthode que nous proposons effectue un processus énumératif booléen adapté à l' ASP et à la nouvelle sémantique. Elle a l'avantage de travailler sur une représentation sous forme de clauses de Horn ayant la même taille que le programme logique d'entrée et travaille à espace constant. En plus, l'énumération est effectuée sur un ensemble restreint de littéraux du programme logique représentant son "strong backdoor". Nous avons aussi proposé une approche pour exploiter les symétries et éviter ainsi l'exploration d'espaces isomorphes dans l'arbre de recherche. Les symétries sont traitées de manière statique en ajoutant dans une phase de prétraitement des contraintes supplémentaires pour les éliminer. Dans cette approche, nous éliminons les symétries existantes uniquement entre les littéraux de l'ensemble "strong backdoor". La seconde partie de la thèse traite les problèmes biologiques via l'approche ASP décrite en première partie. Durant ces dernières décennies, la biologie a connu un véritable essor sur plusieurs plans. De nouveaux champs d’applications et d’étude comme les biotechnologies, les nanotechnologies, et la bio-informatique ont pris une grande place dans le champ d’investigation des chercheurs. La biologie présente alors, de nouveaux challenges aux informaticiens et à l’intelligence artificielle en particulier, et l'ASP ne déroge pas à cette règle. Nous nous sommes intéressés ici à la détection d'attracteurs dans les réseaux génétiques. Les attracteurs sont importants pour étudier la fonction biologique d'une cellule. Dans un premier temps, nous avons proposé une méthode dédiée à la recherche de configurations et de cycles stables pour un mode de mise à jour choisi (synchrone ou asynchrone). Dans cette approche, la détection d'attracteurs passe par la simulation de la dynamique des réseaux génétiques, puis par la vérification de l'existence des attracteurs. Dans un second temps, une approche pour la détection d’attracteurs est proposée. Dans celle-ci, aucune simulation n'est effectuée. L'approche se concentrera sur le cas particulier des circuits qui jouent un rôle important dans les systèmes biologiques. Nous avons mentionné qu'il existe certaines propriétés communes entre les circuits et la programmation logique, en particulier pour la nouvelle sémantique. En plus de la recherche d'attracteurs, nous avons traité la formalisation et le raisonnement sur des réseaux de gènes. Notre représentation logique présente l'avantage d'être flexible et peut être aisément mise à jour grâce à l'utilisation d'une logique non-monotone. Ces aspects sont très importants en raison du caractère incomplet inhérent aux informations biologiques.

Answer Set Programming (ASP) is a declarative programming paradigm based on the semantics of stable models. The idea behind the ASP is to encode a computational problem into a set of logical rules, the stable models of the logical program correspond to the solution of the initial computational problem. The high expressiveness of ASP, combined with the growing number of its applications, has made the implementation of ASP solvers an important research topic. In the first part of this thesis, we study the use of a new semantics for logic programs to design an ASP system. This semantics gives us the ability to compute all stable models of a logic program, and to compute extra-models when the logic program does not have stable models. We propose a method that has the advantage of using a set of Horn clauses having the same size as the input logic program and working on a constant space. In addition, the enumeration is done on a restricted set of logical program literals representing the "strong backdoor" set. Subsequently, we proposed an approach to take advantage of the symmetries and thus avoid the exploration of isomorphic spaces in the search tree. The symmetries are statically processed by adding additional constraints in a pretreatment phase to eliminate them. In this approach, we eliminate the existing symmetries only between the literals of the "strong backdoor" set. The second part of the thesis, we apply our ASP approach. Indeed, during the last decades, biology has become extremely popular in many areas. New fields of application and study such as biotechnologies, nanotechnologies, and bioinformatics have taken a place in the research field. Biology then presents new challenges for computer scientists and artificial intelligence in particular, and ASP does not depart from this rule. Hence,we deal in this thesis with the detection of attractors in Genetic networks. Attractors are important for studying the biological function of a cell. First, we proposed a method to search for configurations and stable cycles for a chosen update mode (synchronous or asynchronous). In this method, attractor detection involves simulating the dynamics of Boolean networks, and then checking for the existence of attractors. Then, in the second step, we proposed an approach for the detection of attractors, in this one no simulation is carried out, the approach will focus on the particular case of circuits that play an important role in biological systems. We have seen that there are some common properties between circuit networks and logic programming, especially with the new semantics. In addition to the search for attractors, we have treated in this thesis the formalization and the reasoning on genes networks. Our logical representation has the advantage of being flexible and easily updatable due to the use of a non-monotonic logic. These aspects are very important because of the incompleteness inherent to the biological knowledge.