Thèmes étudiés

Un des problèmes centraux en Informatique Fondamentale est la représentation et la manipulation efficace des expressions booléennes. Une bonne compréhension des diverses représentations des fonctions booléennes et de leurs propriétés fondamentales, en particulier des divers types de complexité qui peuvent être définis sur ces représentations et des distributions de probabilité qui leur sont associées, a un intéret évident dans nombre de domaines: conception de circuits, satisfiabilité de fonctions booléennes, avec les phénomènes de seuil sous-jacents, résolution de contraintes, etc. Par exemple, Lefmann et Savicky ont établi un lien entre un certain type de  représentation arborescente d'une fonction booléenne (les arbres Et/Ou) et sa complexité: la connaissance de la probabilité d'apparition d'une fonction f  permet de donner des bornes sur la complexité de f. Les techniques énumératives, analytiques et probabilistes développées pour l'étude des structures arborescentes trouvent ici un nouveau champ d'application.

Le travail développé dans l'équipe concerne d'abord la définition et l'évaluation des probabilités en arbre sur les fonctions booléennes, ainsi que l'étude des liens entre la probabilité d'une fonction booléenne et sa complexité en arbre (plus petite taille d'un arbre représentant la fonction).

Un deuxième axe s'intéresse à la comparaison de la puissance d'expression de différents systèmes du calcul propositionnel; cette puissance d'expression est en général liée au comportement de diverses classes de tautologies dans le système en question.

Naturellement, des questions similaires (dénombrement des formules de taille donnée, lois de probabilité pouvant être définies sur l'ensemble des formules constructibles dans un systeme donné) se posent lorsqu'on sort du calcul des propositions. Nous avons choisi d'étudier les lambda-termes, qui peuvent être vus comme des formules logiques construites sur un seul quantificateur -- et qui sont aussi, vus sous un autre angle, des graphes dirigés acycliques. Alors que les formules du calcul des propositions restaient représentables par des arbres, pour lesquels les outils de la combinatoire analytique sont particulierement appropriés, l'étude des lambda-termes fait apparaître des comportements nouveaux, et requiert des techniques elles aussi nouvelles.

Enfin, le dernier thème développé concerne les problemes de satisfiabilité. Chercher la probabilité qu'une formule booléenne ne soit pas satisfiable revient à chercher la probabilité qu'elle calcule Faux: ce probleme peut être approché par les mêmes techniques que celles utilisées pour étudier les distributions en arbres des fonctions booléennes -- si ce n'est que la forme tres particulière des formules concernées impose, là aussi, l'emploi de nouvelles techniques.

Publications

Journaux internationaux

 Dominique Barth, Loubna Echabbi, and Chahinez Hamlaoui. Optimal transit price negotiation: The distributed learning perspectives. Journal of Universal Computer Science, 14(5):745-765, 2008.

 Lélia Blin, Pierre Fraigniaud, Nicolas Nisse, and Sandrine Vial. Distributed chasing of network intruders by mobile agents. Theoretical Computer Science (TCS), 399:12-37, 2008. [ DOI ]

 Alexander Chistov, Hervé Fournier, Pascal Koiran, and Sylvain Perifel. On the construction of a family of transversal subspaces over finite fields. Linear Algebra and its Applications, 429(2-3):589-600, 2008.

 Hervé Fournier and Guillaume Malod. Universal relations and #P-completeness. Theoretical Computer Science, 2008. To appear. [ DOI ]

 Romain Rivière, Dominique Barth, Johanne Cohen, and Alain Denise. Shuffling biological sequences with motif constraints. Journal of Discrete Algorithms, 6:192-204, 2008.

 Dominque Barth, johanne Cohen, and Taoufik Faik. On the b-continuity property of graphs. Discrete Applied Mathematics, 155(13):1761-1768, 2007.

 Hervé Fournier and Antoine Vigneron. A tight lower bound for computing the diameter of a 3D convex polytope. Algorithmica, 49(3):245-257, 2007.

 D. Barth, P. Berthomé, M. Diallo, and A. Ferreira. Revisiting parametric multi-terminal problems: Maximum flows, minimum cuts and cut-tree computations. Discrete Optimization, 3(3):195-205, 2006. [ DOI ]

 Dominique Barth, Johanne Cohen, and Corentin Durbach. Multicast tree allocation algorithms for distributed interactive simulation. International Journal of High Performance Computing and Networking (IJHPCN), 4(3/4):137-151, 2006.

 Dominique Barth, Johanne Cohen, Lynda Gastal, Thierry Mautor, and Rousseau Stephane. Algorithmic study of complexity of two quality-of-service packet models in an optical slotted ring network. Journal of Optical Networking, 5(11):780-789, 2006.

 Dominique Barth and Hervé Fournier. A degree bound on decomposable trees. Discrete Mathematics, 306(5):469-477, 2006.

 Sylvie Corteel and Jeremy Lovejoy. An iterative–bijective approach to generalizations of schur’s theorem. European Journal of Combinatorics, 27(4):496-512, 2006. [ DOI ]

 Dominique Barth, Pascal Berthomé, and Paraskevi Fragopoulou. The complexity of the maximal requests satisfaction problem in multipoint communication. Parallel Processing Letters, 15(1-2):209-222, 2005.

 Sylvie Corteel, Carla D. Savage, and H.S. Wilf. A note on partitions and compositions defined by inequalities. Integers, 5: , 2005.

 Sylvie Corteel, Mario Valencia-Pabon, and Juan-Carlos Vera. On approximating the b-chromatic number. Discrete Applied Mathematics, 146(1):106-110, 2005. [ DOI ]

 Dominique Barth and Pascal Berthomé. Periodic gossiping in commuted networks. Theory of Computing Systems, 37(5):559-584, 2004.

 Dominique Barth, Pascal Berthomé, and Johanne Cohen. The eulerian stretch of a network topology and the ending guarantee of a convergence routing. Journal of Interconnection Networks, 5(2):93-109, 2004.

 Marie-Pierre Béal, Anne Bergeron, Sylvie Corteel, and Mathieu Raffinot. An algorithmic view of gene teams. Theoretical Computer Science, 320(2-3):395-418, 2004. [ DOI ]

 B. Chauvin, P. Flajolet, D. Gardy, and B. Gittenberger. And/or trees revisited. Combinatorics, Probability and Computing, 13(4-5):475-497, 2004.

 Sylvie Corteel, Alain Goupil, and Gilles Schaeffer. Content evaluation and class symmetric functions. Advances in Mathematics, 188(2):315-336, 2004. [ DOI ]

 Sylvie Corteel and P. Hitczenko. Multiplicity and number of parts in overpartitions. Annals of Combinatorics, 8:287-301, 2004.

 Sylvie Corteel and Jeremy Lovejoy. Overpartitions. Trans. of the Amer. Math. Soc, 356:1623-1635, 2004.

 Sylvie Corteel, Jeremy Lovejoy, and A.J. Yee. Infinite generating function and frobenius partitions. Mathematics and Computer Science III,  :15-24, 2004.

 Sylvie Corteel and Carla D. Savage. Lecture hall theorems, -series and truncated objects. J. Comb. Theory, Ser. A, 108(2):217-245, 2004. [ DOI ]

 Sylvie Corteel and Carla D. Savage. Partitions and compositions defined by inequalities. Ramanujan journal, 8:357-381, 2004.

 Michael Drmota, Danièle Gardy, and Bernhard Gittenberger. General urn models with several types of balls and gaussian limiting fields. Random Struct. Algorithms, 24(1):75-103, 2004. [ DOI ]

Conférences internationales avec comité de programme et actes

 A. Genitrini, J. Kozik, and G. Matecki. On the density and the structure of the peirce-like formulae. In Fifth Colloquium on Mathematics and Computer Science : Algorithms, Trees, Combinatorics and Probabilities, Blaubeuren, Allemagne, September 2008.

 H. Fournier, D. Gardy, A. Genitrini, and B. Gittenberger. Complexity and limiting ratio of boolean functions over implication. In International Conference on Mathematical Foundations of Computer Science (MFCS), Torun, Pologne, August 2008.

 Dominique Barth, Olivier Bournez, Octave Boussaton, and Johanne Cohen. Distributed learning of wardrop equilibria. In 7th International Conference on Unconventional Computation (UC), 2008.

 Romain Ravaux. Decomposing trees with large diameter. In Seventh Cologne-Twente workshop on graphs and combinatorial optimization, Gargano, Italy, 2008.

 D. Barth, L. Echabbi, and C. Hamlaoui. Transit price negotiation: Decentralized learning of optimal strategies with incomplete information. In Proc. Next Generation Internet Networks NGI 2008, pages 23-30, 2008. [ DOI ]

 Yacine Benallouche and Dominique Barth. Optimized multicast tree for handover in a two-nodes mobile network architecture based on a all-ip infrastructure. In The Fourth International Conference on Wireless and Mobile Communications ICWMC. IARIA, IEEE Computer Society Press and IEEE XPlore Digital Library, 2008.

 Hervé Fournier and Antoine Vigneron. Fitting a step function to a point set. In 16th Annual European Symposium on Algorithms (ESA), 2008. To appear.

 Oliver Teytaud and Hervé Fournier. Lower bounds for evolution strategies using VC-dimension. In 10th International Conference on Parallel Problem Solving From Nature (PPSN), 2008. To appear.

 Marc-Antoine Weisser, Joanna Tomasik, and Dominique Barth. Congestion Avoiding Mechanism Based on Inter-domain Hierarchy. In Springer Berlin / Heidelberg, editor, IFIP Networking, volume 4982, pages 470-481. LNCS, 2008. [ DOI ]

 Dominique Barth, Johanne Cohen, Loubna Echabbi, and Chahinez Hamlaoui. Transit prices negotiation: Combined repeated game and distributed algorithmic approach. In NET-COOP, pages 266-275, 2007.

 H. Fournier, D. Gardy, A. Genitrini, and M. Zaionc. Classical and intuitionnistic logics are asymptotically identical. In International Conference on Computer Science and Logic (CSL'07), number 4646 in LNCS, pages 173-193, Lausanne, Suisse, 2007. Springer-Verlag.

 A. Genitrini, J. Kozik, and M. Zaionc. Intuitionistic vs. classical tautologies, quantitative comparison. In Types for Proofs and Programs, volume 4941, pages 100-109, Cividale del Friuli, Italie, 2007. LNCS.

 Lélia Blin, Pierre Fraigniaud, Nicolas Nisse, and Sandrine Vial. Distributed chasing of network intruders by mobile agents. In SIROCCO, 2006.

 Hervé Fournier and Guillaume Malod. Universal relations and #P-completeness. In 6th Conference on Algorithms and Complexity (CIAC), volume 3998, pages 368-379. LNCS, 2006.

 Hervé Fournier and Antoine Vigneron. Lower bounds for geometric diameter problems. In (Latin American Theoretical Informatics Symposium) LATIN, pages 467-478, 2006.

 N. Pisanti, A. Carvalho, L. Marsan, and M.-F. Sagot. RISOTTO: Fast extraction of motifs with mismatches. In Latin American Theoretical INformatics (LATIN), volume 3887 of LNCS, pages 757-768. Springer-Verlag, 2006.

 D. Gardy. Random boolean expressions. In R. David, D. Gardy, P. Lescanne, and M. Zaionc, editors, Colloquium on Computational Logic and Applications, AF, pages 1-36, Chambéry, France, June 2005. DMTCS Proceedings. Invited paper.

 D. Gardy and A. Woods. Lower bounds on probabilities for boolean functions. In C. Martinez, editor, First Intern. Conf. on the Analysis of Algorithms, volume AD, pages 139-146, Barcelona, Spain, June 2005. DMTCS Proceedings.

 Dominique Barth, Lélia Blin, Loubna Echabbi, and Sandrine Vial. Distributed cost management in a selfish multi-operators BGP network. In EuroNGI, 2005.

 Laurent Ciarletta and Chahinez Hamlaoui. Enabling autoconfiguration of the management plane using service discovery protocols. In International computer systems and information technology conference (ICSIT), 2005.

 D. Barth, J. Cohen, L. Gastal, T. Mautor, and S. Rousseau. Fixed size and variable size packet models in an optical ring network: Complexity and simulations. In International Symposium on Computer And Information Sciences (ISCIS), number 3280 in LNCS, pages 238-246. Springer-Verlag, 2004.

Conférences nationales avec comité de programme et actes

 Dominique Barth, Pascal Berthomé, and Madiagne Diallo. An analysis of gomory-hu cut-trees relationship. In Symposium of the Brazilian Operational Research Society, 2008.

 Dominique Barth, Alain Denise, Alexis Lamiable, Franck Quessette, and Sandrine Vial. Classification automatique en famille des jonctions triples de l'ARN. In JOBIM (Journées Ouvertes Biologie Informatique Mathématiques), 2008. Short Paper.

 D. Barth, P. Berthomé, and M. Diallo. Detecting flows congesting a target network link. In C.M.H. de Figueiredo P. Feofiloff and Y. Wakabayashi, editors, 2nd Brazilian Symposium on Graphs, Algorithms and Combinatorics (GRACO), volume 19, pages 233-239. Electronic Notes in Discrete Mathematics, 2005.

Workshops internationaux avec comité de programme

 Dominique Barth, Loubna Echabbi, and Chahinez Hamlaoui. The distributed learning perspective(extended abstract). In Second EuroNGI Workshop on Socio-economic Aspects of Next Generation Internet, 2007.

 Dominique Barth, Johanne Cohen, Loubna Echabbi, and Chahinez Hamlaoui. Transit price negotiation : a repeated game approch (extended abstract). In First EuroNGI IA.8.6 Workshop on Socio-economic Aspects of Next Generation Internet, 2006.

 Dominique Barth, Loubna Echabbi, Chahinez Hamlaoui, and Sandrine Vial. An economic and algorithmic model for QoS provisioning BGP interdomain network. In Workshop on QoS and Traffic Control, 2005.

 Dominique Barth, Jean-Michel Fourneau, David Nott, and Dominique Chiaroni. Routing and qos in an all-optical packet network. In IEEE Workshop on Optical Burst Switching, volume 2, pages 1063-1072, 2005. [ DOI ]

 D. Barth and L. Echabbi. Distributed multi-link auctions for network resource reservation and pricing. In International Workshop on Advanced Internet Charging and QoS Technologies (ICQT), volume 3266 of LNCS. Springer Verlag, 2004.

Autres conférences et workshops

 Christian Cadéré, Dominique Barth, and Sandrine Vial. Algorithms for services and network resources allocation using graph embedding. In Rencontres Francophones sur les aspects Algorithmiques des Télécommunications (Algotel), 2008.

 Lynda Gastal, Romain Ravaux, and Stéphane Rousseau. Routage eulérien pour un réseau optique : dimensionnement des routeurs. In Francoro V / ROADEF, Grenoble, France, 2007.

 Dominique Barth, Alain Denise, and Romain Rivière. Motifs enumeration algorithms in biological networks. In Journée thématique "Réseaux d'interaction : analyse, modélisation et simulation" (RIAMS), 2006.

 Lélia Blin, Pierre Fraigniaud, Nicolas Nisse, and Sandrine Vial. Encerclement réparti d'un fugitif, dans un réseau, par des agents mobiles. In Rencontres Francophones sur les aspects Algorithmiques des Télécommunications (Algotel), 2006.

 Dominique Barth and Benjamin Cohen. Ordonnancement d'expressions arithmétiques avec valeurs communes. In 7eme congrès de la société française de recherche opérationnelle et d'aide à la décision (ROADEF), 2005.

 Dominique Barth, Antoine Joulie, and Maria Pentcheva. Séparation de graphes pour l'identification de voies métaboliques. In Journée thématique "Réseaux d'interaction : analyse, modélisation et simulation" (RIAMS), 2005.

 Dominique Barth and Alexis Lamiable. Algorithmes de planification d'expériences pour la détermination de réseaux d'interactions de protéines. In Journée thématique "Réseaux d'interaction : analyse, modélisation et simulation" (RIAMS), 2005.

 Dominique Barth, T. Lanquetin, and Thierry Mautor. Pré-optimisation et conception "on-line" de tournées de techniciens de maintenance. In 7eme congrès de la société française de recherche opérationnelle et d'aide à la décision (ROADEF), 2005.

 Dominique Barth, Thierry Mautor, Mélanie Ponchie, and Franck Quessette. Dimensionnement des réseaux dans fado : une première approche. In 7eme congrès de la société française de recherche opérationnelle et d'aide à la décision (ROADEF), 2005.

 Henry Amet, Johanne Cohen, Freddy Deppner, Marie-Claude Portmann, and Stéphane Rousseau. Un problème d'ordonnancement de messages : Partie 1 modélisations. In 6ème congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF), pages 54-55, 2005.

 Sylvie Corteel, G. Louchard, and R. Pemantle. Common intervals in permutations. In Third Colloquium on Mathematics and Computer Science, 2004.

 Chérif Boutammine. Covering problem for sky picture. In Conference on Modelisation, Computation and Optimization MCO'08 ...

Posters

 Dominique Barth, Jean-Michel Fourneau, and David Nott. Two cycles routing and end to end delay bound in all optical network. Photonics in Switching 2008, Poster Session, 2008.

 M. Mabrouki, J.-P. Comet, P. Le Gall, and S. Vial. Identifying independent sub-networks of biological regulatory networks for ensuring preservation of observations issued from biological experiments. Poster - Ecole sur la Modélisation de systèmes biologiques complexes dans le contexte de la génomique., 2008.

 Dominique Barth, Pascal Berthomé, Jean-Michel Fourneau, Christian Laforest, and Sandrine Vial. Performance evaluation of short-cut eulerian routing. International Conference on Next Generation Internet, 2005.

 R. Brak, Sylvie Corteel, A. Rechnitzer, and J. Essam. A combinatorial derivation of the pasep algebra. Poster - FPSAC, 2005.

 S. Brouillet, E. Ollivier, L. Marsan, and A. Vanet. HIV : from structure to therapeutic target. Poster - JOBIM (Journées Ouvertes Biologie Informatique Mathématiques), 2005.

 Sylvie Corteel, S. Lee, and Carla D. Savage. Enumeration of sequences constrained by the ratio of consecutive parts. Poster - FPSAC, 2005.

 L. Marsan, S. Brouillet, E. Ollivier, and A. Vanet. HIV : towards stable multi-therapies. Poster - JOBIM (Journées Ouvertes Biologie Informatique Mathématiques), 2005.

 E. Ollivier, S. Brouillet, L. Marsan, and A. Vanet. HIV : a medicine for one day, a medicine forever. Poster - JOBIM (Journées Ouvertes Biologie Informatique Mathématiques), 2005.

 A. Vanet, E. Ollivier, L. Marsan, and S. Brouillet. HIV database. Poster - JOBIM (Journées Ouvertes Biologie Informatique Mathématiques), 2005.

Brevets

 A. Vanet, S. Brouillet, L. Marsan, and E. Ollivier. Method for identifying motifs and/or combinations of motifs having a boolean state of predetermined mutation in a set of sequences and its applications. Patent pending, 2006. Continuation In Part (CIP) n. 13052-US-02 du brevet n 10/734023 (CNRS).

Présentation Equipe ALCAAP

Algorithmique, combinatoire analytique et applications

Les racines de l'équipe se situent dans les fondements de l'informatique : théorie des graphes, algorithmique, complexité, combinatoire énumérative et analytique. L'approche scientifique de l'équipe se caractérise par des contributions à la fois dans ces domaines fondamentaux mais aussi dans les applications, à l'industrie ou à d'autres domaines scientifiques (tels que la bioinformatique ou la logique).

Quand on cherche la solution d'un problème complexe, la première étape consiste à comprendre ce problème en profondeur (propriétés structurelles, choix d'un modèle adéquat, lien avec les problèmes classiques). Ce travail permet de concevoir des algorithmes appropriés pour résoudre le problème initial. L'analyse du comportement de cet algorithme est ensuite effectuée à l'aides d'outils tels que la simulation ou l'analyse mathématique, permettant ainsi de garantir ses performances en moyenne ou dans le pire cas.

Les membres de l'équipe proviennent de différents domaines de l'informatique. Une constante au sein de l'équipe est la forte interaction entre ses membres et avec le reste du laboratoire, ainsi que les collaborations internationales ou avec des chercheurs travaillant dans l'industrie.


Thématiques:

Algorithmique et théorie des graphes

Analyse d'algorithmes et combinatoire

Fonctions booléennes: représentations, probabilités et complexité

Complexité de problèmes géométriques

Informatique pour la biologie

Algorithmique pour les Réseaux Biologiques : Axe transversal ARBio (ALCAAPEPRI)

Réseau, Routage, Performance : Axe transversal RRP (ALCAAPEPRIASR)

Performances d'un solveur de contraintes

En collaboration avec deux chercheurs de Nantes (X. Lorca et C. Truchet), nous avons initié une étude visant a évaluer les performances d'un solveur de contraintes. Les premiers travaux ont porté sur l'analyse de la contrainte AllDifferent: quelle est la probabilité qu'elle soit (ou reste) consistante aux bornes?

J. du Boisberranger, D. Gardy, X. Lorca, C. Truchet. When is it worthwhile to propagate a constraint? A probabilistic analysis of ALLDIFFERENT. Siam workshop on Analytic Algorithmics and Combinatorics (ANALCO), January 2013, New Orleans (USA).

Modèles d'urnes et allocations aléatoires-old

Les modèles d'urnes sont parmi les modèles les plus courants d'allocations aléatoires, et peuvent être utilisés pour représenter nombre de phénomènes informatiques (l'exemple le plus connu est sans doute le hachage), en reliant le coût que l'on souhaite étudier à un paramètre tel que le nombre d'urnes ayant une certaine propriété. Leur comportement « statique », à un instant donné, peut souvent se décrire par des séries génératrices du type « grande puissance de fonction », et est alors analysable par les techniques classiques en analyse d'algorithmes ; il conduit fréquemment à des distributions limites suivant des lois de Poisson ou Gaussiennes. Par contraste, l'évolution « dynamique », au fil du temps et des mises à jour, est plus difficile à analyser.

Les recherches de l'équipe, parties de l'étude de modèles particuliers (bases de données et apprentissage), ont permis de dégager des classes de modèles susceptibles d'un traitement uniforme. Nous avons commencé par étudier des modèles « semi-dynamiques », où seules les requêtes sans modification des données et les insertions sont autorisées : pour cette classe, et pour certaines valeurs des paramètres de départ (« domaine central »), le coût étudié peut être décrit asymptotiquement par un processus limite Gaussien.  Ces résultats peuvent être étendus à des modèles autorisant la suppression de données, ainsi qu'au cas multi-dimensionnel.

Publications

M. Drmota, D. Gardy and B. Gittenberger. General urn models with several types of balls and Gaussian limiting fields. Random Structures and Algorithms, Vol.24 No.1, 2004.

M. Drmota, D. Gardy et B. Gittenberger. A unified presentation of some urn models. Algorithmica, Special issue on the average-case analysis of algorithms, Vol. 29 No 1/2,  pp 120-147, 2001.

Our website is protected by DMC Firewall!