Publications

Warning: fopen(/users/rossin/.webdir/ANR/Magnum/www/wp-content/plugins/bib3html/data/biblio-ponty-MAGNUM.bib.cached.bib): failed to open stream: Permission denied in /users/rossin/.webdir/ANR/Magnum/www/wp-content/plugins/bib3html/bib3html.php on line 86 Failed to write file/users/rossin/.webdir/ANR/Magnum/www/wp-content/plugins/bib3html/data/biblio-ponty-MAGNUM.bib.cached.bib - check directory permission according to your Web server privileges. Warning: fopen(/users/rossin/.webdir/ANR/Magnum/www/wp-content/plugins/bib3html/lib/../cache/e4b5e6342b8159613cd90d391797a47b.cached.html): failed to open stream: Permission denied in /users/rossin/.webdir/ANR/Magnum/www/wp-content/plugins/bib3html/lib/Bib3Html.HtmlCache.php on line 61 Warning: fopen(/users/rossin/.webdir/ANR/Magnum/www/wp-content/plugins/bib3html/lib/../cache/d719ce1b6ba9b1a1572f5782217aacb9.cached.html): failed to open stream: Permission denied in /users/rossin/.webdir/ANR/Magnum/www/wp-content/plugins/bib3html/lib/Bib3Html.HtmlCache.php on line 61

Liste des publications de Magnum extraite de Hal :

  • [2013,article] bibtex Go to document
    O. Cheong, X. Goaoc, and C. Nicaud, "Set Systems and Families of Permutations with Small Traces," European Journal of Combinatorics, vol. 34, pp. 229-239, 2013.
    @ARTICLE{cheong:hal-00752064, author = {Cheong, Otfried and Goaoc, Xavier and Nicaud, Cyril},
      title = {{Set Systems and Families of Permutations with Small Traces}},
      journal = {{European Journal of Combinatorics}},
      year = {2013},
      volume = {34},
      pages = {229-239},
      owner = {Yawn},
      publisher = {Elsevier},
      timestamp = {2013.03.11},
      url = {http://hal.inria.fr/hal-00752064}
    }
  • [2013,inproceedings] bibtex Go to document
    V. Reinharz, Y. Ponty, and J. Waldispühl, "A linear inside-outside algorithm for correcting sequencing errors in structured RNA sequences," in RECOMB – 17th Annual International Conference on Research in Computational Molecular Biology – 2013, Beijing, Chine, 2013.
    @INPROCEEDINGS{reinharz:hal-00766781, author = {Reinharz, Vladimir and Ponty, Yann and Waldisp{\"u}hl, J{\'e}r{\^o}me},
      title = {{A linear inside-outside algorithm for correcting sequencing errors in structured RNA sequences}},
      booktitle = {{RECOMB - 17th Annual International Conference on Research in Computational Molecular Biology - 2013}},
      year = {2013},
      address = {Beijing, Chine},
      owner = {Yawn},
      timestamp = {2013.03.11},
      url = {http://hal.inria.fr/hal-00766781}
    }
  • [2013,inproceedings] bibtex Go to document
    E. Senter, S. Sheikh, I. Dotu, Y. Ponty, and P. Clote, "Using the Fast Fourier Transform to accelerate the computational search for RNA conformational switches (extended abstract)," in RECOMB – 17th Annual International Conference on Research in Computational Molecular Biology – 2013, Beijing, Chine, 2013.
    @INPROCEEDINGS{senter:hal-00766780, author = {Senter, Evan and Sheikh, Saad and Dotu, Ivan and Ponty, Yann and Clote, Peter},
      title = {{Using the Fast Fourier Transform to accelerate the computational search for RNA conformational switches (extended abstract)}},
      booktitle = {{RECOMB - 17th Annual International Conference on Research in Computational Molecular Biology - 2013}},
      year = {2013},
      address = {Beijing, Chine},
      owner = {Yawn},
      timestamp = {2013.03.11},
      url = {http://hal.inria.fr/hal-00766780}
    }
  • [2013,article] bibtex Go to document
    A. Lorenz and Y. Ponty, "Non-redundant random generation algorithms for weighted context-free languages," Theoretical Computer Science, 2013.
    @ARTICLE{lorenz:inria-00607745, author = {Lorenz, Andy and Ponty, Yann},
      title = {{Non-redundant random generation algorithms for weighted context-free languages}},
      journal = {{Theoretical Computer Science}},
      year = {2013},
      pages = {To appear},
      owner = {Yawn},
      publisher = {Elsevier},
      timestamp = {2013.03.11},
      url = {http://hal.inria.fr/inria-00607745}
    }
  • [2012,inproceedings] bibtex Go to document
    J. Waldispühl, B. Berger, S. Devadas, P. Clote, and Y. Ponty, "Efficient Algorithms to Explore the RNA Mutational Landscape," in DM – SIAM Conference on Discrete Mathematics – 2012, Halifax, Canada, 2012.
    @INPROCEEDINGS{waldispuhl:hal-00723333, author = {Waldisp{\"u}hl, J{\'e}r{\^o}me and Berger, Bonnie and Devadas, Srinivas and Clote, Peter and Ponty, Yann},
      title = {{Efficient Algorithms to Explore the RNA Mutational Landscape}},
      booktitle = {{DM - SIAM Conference on Discrete Mathematics - 2012}},
      year = {2012},
      address = {Halifax, Canada},
      organization = {SIAM Activity Group on Discrete Mathematics},
      owner = {Yawn},
      timestamp = {2013.03.11},
      url = {http://hal.inria.fr/hal-00723333}
    }
  • [2012,inproceedings] bibtex Go to document
    J. Du Boisberranger, D. Gardy, and Y. Ponty, "The weighted words collector," in AOFA – 23rd International Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms – 2012, Montreal, Canada, 2012, pp. 243-264.
    @INPROCEEDINGS{duboisberranger:hal-00666399, author = {Du Boisberranger, J{\'e}r{\'e}mie and Gardy, Dani{\`e}le and Ponty, Yann},
      title = {{The weighted words collector}},
      booktitle = {{AOFA - 23rd International Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms - 2012}},
      year = {2012},
      editor = {Nicolas, Broutin (INRIA, France) and Luc, Devroye (McGill, Cana},
      volume = {dmAQ01},
      series = {DMTCS Proceedings},
      pages = {243--264},
      address = {Montreal, Canada},
      organization = {Nicolas, Broutin (INRIA, France) and Luc, Devroye (McGill, Canada)},
      publisher = {DMTCS},
      keywords = {Coupon Collector Problem;Waiting Time;Random Generation;Weighted Context-free Languages},
      owner = {Yawn},
      timestamp = {2013.03.11},
      url = {http://hal.inria.fr/hal-00666399}
    }
  • [2012,article] bibtex Go to document
    E. Senter, S. Sheikh, I. Dotu, Y. Ponty, and P. Clote, "Using the Fast Fourier Transform to Accelerate the Computational Search for RNA Conformational Switches," PLoS ONE, vol. 7, iss. 12, p. 50506, 2012.
    @ARTICLE{senter:hal-00769740, author = {Senter, Evan and Sheikh, Saad and Dotu, Ivan and Ponty, Yann and Clote, Peter},
      title = {{Using the Fast Fourier Transform to Accelerate the Computational Search for RNA Conformational Switches}},
      journal = {{PLoS ONE}},
      year = {2012},
      volume = {7},
      pages = {e50506},
      number = {12},
      month = Dec, doi = {10.1371/journal.pone.0050506},
      owner = {Yawn},
      publisher = {Public Library of Science},
      timestamp = {2013.03.11},
      url = {http://hal.inria.fr/hal-00769740}
    }
  • [2012,inproceedings] bibtex Go to document
    S. Sheikh, R. Backofen, and Y. Ponty, "Impact Of The Energy Model On The Complexity Of RNA Folding With Pseudoknots," in CPM – 23rd Annual Symposium on Combinatorial Pattern Matching – 2012, Helsinki, Finlande, 2012.
    @INPROCEEDINGS{sheikh:hal-00670232, author = {Sheikh, Saad and Backofen, Rolf and Ponty, Yann},
      title = {{Impact Of The Energy Model On The Complexity Of RNA Folding With Pseudoknots}},
      booktitle = {{CPM - 23rd Annual Symposium on Combinatorial Pattern Matching - 2012}},
      year = {2012},
      editor = {Juha K{\"a}rkk{\"a}inen and Jens Stoye },
      pages = {TBA},
      address = {Helsinki, Finlande},
      abstract = {{Predicting the folding of an RNA sequence, while allowing general pseudoknots (PK), consists in finding a minimal free-energy matching of its $n$ positions. Assuming independently contributing base-pairs, the problem can be solved in $\Theta(n^3)$-time using a variant of the maximal weighted matching. By contrast, the problem was previously proven NP-Hard in the more realistic nearest-neighbor energy model. In this work, we consider an intermediate model, called the stacking-pairs energy model. We extend a result by Lyngs\o, showing that RNA folding with PK is NP-Hard within a large class of parametrization for the model. We also show the approximability of the problem, by giving a practical $\Theta(n^3)$ algorithm that achieves at least a $5$-approximation for any parametrization of the stacking model. This contrasts nicely with the nearest-neighbor version of the problem, which we prove cannot be approximated within any positive ratio, unless $P=NP$.}},
      affiliation = {Laboratoire d'informatique de l'{\'e}cole polytechnique - LIX , AMIB - INRIA Saclay - Ile de France , Albert-Ludwigs University - ALBERT-LUDWIGS UNIVERSITY},
      audience = {internationale },
      hal_id = {hal-00670232},
      keywords = {RNA folding;General pseudoknots;Hardness;Inapproximability},
      language = {Anglais},
      pdf = {http://hal.inria.fr/hal-00670232/PDF/NPCompleteness-Stacking.pdf},
      url = {http://hal.inria.fr/hal-00670232}
    }
  • [2012,inproceedings] bibtex Go to document
    P. Rinaudo, Y. Ponty, D. Barth, and A. Denise, "Tree decomposition and parameterized algorithms for RNA structure-sequence alignment including tertiary interactions and pseudoknots," in WABI – 12th Workshop on Algorithms in Bioinformatics – 2012, Ljubljana, Slovénie, 2012.
    @INPROCEEDINGS{rinaudo:hal-00708580, author = {Rinaudo, Philippe and Ponty, Yann and Barth, Dominique and Denise, Alain},
      title = {{Tree decomposition and parameterized algorithms for RNA structure-sequence alignment including tertiary interactions and pseudoknots}},
      booktitle = {{WABI - 12th Workshop on Algorithms in Bioinformatics - 2012}},
      year = {2012},
      editor = {Ben Raphael and Jijun Tang },
      address = {Ljubljana, Slov{\'e}nie},
      note = {Support from the DIGITEO RNAomics project },
      abstract = {{We present a general setting for structure-sequence comparison in a large class of RNA structures that unifies and generalizes a number of recent works on specific families on structures. Our approach is based on tree decomposition of structures and gives rises to a general parameterized algorithm, where the exponential part of the complexity depends on the family of structures. For each of the previously studied families, our algorithm has the same complexity as the specific algorithm that had been given before.}},
      affiliation = {Laboratoire de Recherche en Informatique - LRI , AMIB - INRIA Saclay - Ile de France , Parall{\'e}lisme, R{\'e}seaux, Syst{\`e}mes d'information, Mod{\'e}lisation - PRISM , Laboratoire d'informatique de l'{\'e}cole polytechnique - LIX , Institut de g{\'e}n{\'e}tique et microbiologie - IGM},
      audience = {internationale },
      hal_id = {hal-00708580},
      keywords = {RNA structure; sequence-structure alignment; tree-decomposition},
      language = {Anglais},
      pdf = {http://hal.inria.fr/hal-00708580/PDF/article.pdf},
      url = {http://hal.inria.fr/hal-00708580}
    }
  • [2012,article] bibtex Go to document
    M. H. Albert, M. D. Atkinson, M. Bouvel, N. Ruv skuc, and V. Vatter, "Geometric grid classes of permutations," Transactions of the American Mathematical Society, p. i, 2012.
    @ARTICLE{albert:hal-00640059, author = {Albert, Michael H. and Atkinson, M. D. and Bouvel, Mathilde and Ru{\v s}kuc, Nik and Vatter, Vincent},
      title = {{Geometric grid classes of permutations}},
      journal = {{Transactions of the American Mathematical Society}},
      year = {2012},
      pages = {{\`a} paraitre},
      owner = {Yawn},
      timestamp = {2013.03.11},
      url = {http://hal.inria.fr/hal-00640059}
    }
  • [2012,inproceedings] bibtex Go to document
    C. Banderier, O. Bodini, Y. Ponty, and H. Tafat, "On the diversity of pattern distributions in combinatorial systems," in Proceedings of the 12th Meeting on Analytic Algorithmics \& Combinatorics, Kyoto, Japon, 2012, pp. 107-116.
    @INPROCEEDINGS{banderier:hal-00643598, author = {Banderier, Cyril and Bodini, Olivier and Ponty, Yann and Tafat, Hanane},
      title = {{On the diversity of pattern distributions in combinatorial systems}},
      booktitle = {{Proceedings of the 12th Meeting on Analytic Algorithmics \& Combinatorics}},
      year = {2012},
      pages = {107--116},
      address = {Kyoto, Japon},
      publisher = {Omnipress},
      abstract = {{It is well known that, under some aperiodicity and irreducibility conditions, the number of occurrences of local patterns within a Markov chain (and, more generally, within the languages generated by weighted regular expressions/automata) follows a Gaussian distribu- tion with both variance and mean in (n). By contrast, when these conditions no longer hold, it has been denoted that the limiting distribution may follow a whole diversity of distributions, including the uniform, power-law or even multimodal distribution, arising as tradeo s between structural properties of the regular expression and the weight/probabilities associated with its transitions/letters. However these cases only partially cover the full diversity of behaviors induced within regular expressions, and a characterization of attainable distributions remained to be provided. In this article, we constructively show that the limiting distribution of the simplest foresee- able motif (a single letter!) may already follow an arbitrarily complex continuous distribution (or cadlag process). We also give applications in random generation (Boltzmann sampling) and bioinformatics (parsimonious segmentation of DNA).}},
      affiliation = {Laboratoire d'informatique de Paris-nord - LIPN , Laboratoire d'informatique de l'{\'e}cole polytechnique - LIX , AMIB - INRIA Saclay - Ile de France},
      audience = {internationale },
      hal_id = {hal-00643598},
      language = {Anglais},
      pdf = {http://hal.archives-ouvertes.fr/hal-00643598/PDF/analco\_soda.pdf},
      url = {http://hal.archives-ouvertes.fr/hal-00643598}
    }
  • [2012,article] bibtex Go to document
    C. Pivoteau, B. Salvy, and M. Soria, "Algorithms for combinatorial structures: Well-founded systems and Newton iterations.," Journal of Combinatorial Theory, Series A, vol. 119, iss. 8, pp. 1711-1773, 2012.
    @ARTICLE{pivoteau:inria-00622853, author = {Pivoteau, Carine and Salvy, Bruno and Soria, Michele},
      title = {{Algorithms for combinatorial structures: Well-founded systems and Newton iterations.}},
      journal = {{Journal of Combinatorial Theory, Series A}},
      year = {2012},
      volume = {119},
      pages = {1711-1773},
      number = {8},
      month = Nov, doi = {10.1016/j.jcta.2012.05.007},
      keywords = {Species theory; analytic combinatorics; generating series; complexity.},
      owner = {Yawn},
      publisher = {Elsevier},
      timestamp = {2013.03.11},
      url = {http://hal.inria.fr/inria-00622853}
    }
  • [2012,article] bibtex Go to document
    C. Banderier and P. Hitczenko, "Enumeration and asymptotics of restricted compositions having the same number of parts," Discrete Applied Mathematics, pp. 1-13, 2012.
    @ARTICLE{banderier:hal-00664192, author = {Banderier, Cyril and Hitczenko, Pawel},
      title = {{Enumeration and asymptotics of restricted compositions having the same number of parts}},
      journal = {{Discrete Applied Mathematics}},
      year = {2012},
      pages = {1-13},
      doi = {10.1016/j.dam.2011.12.011},
      keywords = {Integer composition; Pairs of combinatorial structures; Local limit theorem; Asymptotics of D-finite sequences; Diagonal of algebraic generating function},
      owner = {Yawn},
      timestamp = {2013.03.11},
      url = {http://hal.inria.fr/hal-00664192}
    }
  • [2012,inproceedings] bibtex Go to document
    B. Morcrette and H. M. Mahmoud, "Exactly Solvable Balanced Tenable Urns with Random Entries via the Analytic Methodology," in AofA’12 – 23rd International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms, Montreal, Canada, 2012, p. pp. 219-232.
    @INPROCEEDINGS{morcrette:hal-00719639, author = {Morcrette, Basile and Mahmoud, Hosam M.},
      title = {{Exactly Solvable Balanced Tenable Urns with Random Entries via the Analytic Methodology}},
      booktitle = {{AofA'12 - 23rd International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms}},
      year = {2012},
      editor = {Nicolas Broutin and Luc Devroye},
      volume = {AQ},
      pages = {pp. 219--232},
      address = {Montreal, Canada},
      month = Jun, keywords = {Polya urn; random structure; combinatorial probability; mixed models; differential equations},
      owner = {Yawn},
      timestamp = {2013.03.11},
      url = {http://hal.inria.fr/hal-00719639}
    }
  • [2012,inproceedings] bibtex Go to document
    A. Carayol and C. Nicaud, "Distribution of the number of accessible states in a random deterministic automaton," in STACS’12 (29th Symposium on Theoretical Aspects of Computer Science), Paris, France, 2012, pp. 194-205.
    @INPROCEEDINGS{carayol:hal-00678213, author = {Carayol, Arnaud and Nicaud, Cyril},
      title = {{Distribution of the number of accessible states in a random deterministic automaton}},
      booktitle = {{STACS'12 (29th Symposium on Theoretical Aspects of Computer Science)}},
      year = {2012},
      editor = {Christoph D{\"u}rr, Thomas Wilke},
      volume = {14},
      pages = {194-205},
      address = {Paris, France},
      month = Mar, publisher = {LIPIcs},
      keywords = {finite automata, random sampling, average complexity},
      owner = {Yawn},
      timestamp = {2013.03.11},
      url = {http://hal.inria.fr/hal-00678213}
    }
  • [2012,inproceedings] bibtex Go to document
    I. Marcovici, A. Busic, N. Fatès, and J. Mairesse, "Density Classification on Infinite Lattices and Trees," in LATIN 2012: Theoretical Informatics, Arequipa, Pérou, 2012, pp. 109-120.
    @INPROCEEDINGS{marcovici:hal-00712614, author = {Marcovici, Ir{\`e}ne and Busic, Ana and Fat{\`e}s, Nazim and Mairesse, Jean},
      title = {{Density Classification on Infinite Lattices and Trees}},
      booktitle = {{LATIN 2012: Theoretical Informatics}},
      year = {2012},
      editor = {David Fernandez-Baca },
      volume = {7256},
      series = {Lecture Notes in Computer Science },
      pages = {109-120},
      address = {Arequipa, P{\'e}rou},
      month = Apr, publisher = {Springer},
      abstract = {{Consider an infinite graph with nodes initially labeled by independent Bernoulli random variables of parameter p. We want to find a (probabilistic or deterministic) cellular automaton or a finite-range interacting particle system that decides if p is smaller or larger than 1/2. Precisely, the trajectories should converge to the uniform configuration with only 0's if p }},
      affiliation = {Laboratoire d'informatique Algorithmique : Fondements et Applications - LIAFA , TREC - INRIA Rocquencourt , MAIA - INRIA Nancy - Grand Est / LORIA},
      audience = {internationale },
      doi = {10.1007/978-3-642-29344-3\_10 },
      hal_id = {hal-00712614},
      keywords = {Cellular automata ; interacting particle systems ; density classification ; percolation},
      language = {Anglais},
      url = {http://hal.archives-ouvertes.fr/hal-00712614}
    }
  • [2012,article] bibtex Go to document
    A. Busic, B. Gaujal, and F. Pin, "Perfect Sampling of Markov Chains with Piecewise Homogeneous Events," Performance Evaluation, vol. 69, iss. 6, pp. 247-266, 2012.
    @ARTICLE{busic:hal-00787997, author = {Busic, Ana and Gaujal, Bruno and Pin, Furcy},
      title = {{Perfect Sampling of Markov Chains with Piecewise Homogeneous Events}},
      journal = {{Performance Evaluation}},
      year = {2012},
      volume = {69},
      pages = {247-266},
      number = {6},
      doi = {10.1016/j.peva.2012.01.003},
      keywords = {Markov chains; Perfect sampling; Queueing systems},
      owner = {Yawn},
      publisher = {Elsevier},
      timestamp = {2013.03.11},
      url = {http://hal.inria.fr/hal-00787997}
    }
  • [2012,article] bibtex Go to document
    A. Levin, M. Lis, Y. Ponty, C. W. O’Donnell, S. Devadas, B. Berger, and J. Waldispühl, "A global sampling approach to designing and reengineering RNA secondary structures.," Nucleic Acids Research, vol. 40, iss. 20, pp. 10041-52, 2012.
    @ARTICLE{levin:hal-00733924, author = {Levin, Alex and Lis, Mieszko and Ponty, Yann and O'Donnell, Charles W and Devadas, Srinivas and Berger, Bonnie and Waldisp{\"u}hl, J{\'e}r{\^o}me},
      title = {{A global sampling approach to designing and reengineering RNA secondary structures.}},
      journal = {{Nucleic Acids Research}},
      year = {2012},
      volume = {40},
      pages = {10041-52},
      number = {20},
      month = Nov, doi = {10.1093/nar/gks768},
      owner = {Yawn},
      publisher = {Oxford University Press},
      timestamp = {2013.03.11},
      url = {http://hal.inria.fr/hal-00733924}
    }
  • [2012,inproceedings] bibtex Go to document
    A. Busic, B. Gaujal, and F. Perronnin, "Perfect Sampling of Networks with Finite and Infinite Capacity Queues," in 19th International Conference on Analytical and Stochastic Modelling Techniques and Applications (ASMTA) 2012, Grenoble, France, 2012, pp. 136-149.
    @INPROCEEDINGS{busic:hal-00788003, author = {Busic, Ana and Gaujal, Bruno and Perronnin, Florence},
      title = {{Perfect Sampling of Networks with Finite and Infinite Capacity Queues}},
      booktitle = {{19th International Conference on Analytical and Stochastic Modelling Techniques and Applications (ASMTA) 2012}},
      year = {2012},
      editor = {Khalid Al-Begain and Dieter Fiems and Jean-Marc Vincent},
      volume = {7314},
      series = {Lecture Notes in Computer Science},
      pages = {136-149},
      address = {Grenoble, France},
      publisher = {Springer},
      doi = {10.1007/978-3-642-30782-9\_10},
      owner = {Yawn},
      timestamp = {2013.03.11},
      url = {http://hal.inria.fr/hal-00788003}
    }
  • [2012,inproceedings] bibtex Go to document
    S. Janssen, L. Paulevé, Y. Ponty, B. Raman, and M. Zytnicki, "Can Probabilistic Model Checking Explore Ribo-Nucleic Acid Folding Space?," in IWBDA – 4th International Workshop on Bio-Design Automation – 2012, San Francisco, États-Unis, 2012.
    @INPROCEEDINGS{janssen:hal-00712557, author = {Janssen, Stefan and Paulev{\'e},
      Lo{\"\i}c and Ponty, Yann and Raman, Balaji and Zytnicki, Matthias},
      title = {{Can Probabilistic Model Checking Explore Ribo-Nucleic Acid Folding Space?}},
      booktitle = {{IWBDA - 4th International Workshop on Bio-Design Automation - 2012}},
      year = {2012},
      address = {San Francisco, {\'E}tats-Unis},
      owner = {Yawn},
      timestamp = {2013.03.11},
      url = {http://hal.inria.fr/hal-00712557}
    }
  • [2012,inproceedings] bibtex Go to document
    M. Bouvel and O. Guibert, "Refined enumeration of permutations sorted with two stacks and a D\_8-symmetry," in FPSAC 2012 (24th International Conference on Formal Power Series and Algebraic Combinatorics), Nagoya, Japon, 2012, pp. 757-768.
    @INPROCEEDINGS{bouvel:hal-00749260, author = {Bouvel, Mathilde and Guibert, Olivier},
      title = {{Refined enumeration of permutations sorted with two stacks and a D\_8-symmetry}},
      booktitle = {{FPSAC 2012 (24th International Conference on Formal Power Series and Algebraic Combinatorics)}},
      year = {2012},
      volume = {AR},
      pages = {757-768},
      address = {Nagoya, Japon},
      owner = {Yawn},
      timestamp = {2013.03.11},
      url = {http://hal.inria.fr/hal-00749260}
    }
  • [2012,inproceedings] bibtex Go to document
    B. Morcrette, "Fully Analyzing an Algebraic Polya Urn Model," in LATIN 2012, LNCS 7256, Arequipa, Pérou, 2012, p. pp. 568-581.
    @INPROCEEDINGS{morcrette:hal-00675936, author = {Morcrette, Basile},
      title = {{Fully Analyzing an Algebraic Polya Urn Model}},
      booktitle = {{LATIN 2012, LNCS 7256}},
      year = {2012},
      editor = {D. Fernandez-Baca Ed. },
      volume = {LNCS 7256},
      pages = {pp. 568--581},
      address = {Arequipa, P{\'e}rou},
      publisher = {Springer-Verlag Berlin Heidelberg},
      abstract = {{This paper introduces and analyzes a particular class of Polya urns: balls are of two colors, can only be added (the urns are said to be additive) and at every step the same constant number of balls is added, thus only the color compositions varies (the urns are said to be balanced). These properties make this class of urns ideally suited for analysis from an "analytic combinatorics" point-of-view, following in the footsteps of Flajolet-Dumas-Puyhaubert, 2006. Through an algebraic generating function to which we apply a multiple coalescing saddle-point method, we are able to give precise asymptotic results for the probability distribution of the composition of the urn, as well as local limit law and large deviation bounds.}},
      affiliation = {Laboratoire d'Informatique de Paris 6 - LIP6 , ALGORITHMS - INRIA Rocquencourt},
      audience = {internationale },
      hal_id = {hal-00675936},
      keywords = {analytic combinatorics; Polya urn models; multiple coalescing saddle-point method; Gaussian local limit law; large deviations},
      language = {Anglais},
      pdf = {http://hal.archives-ouvertes.fr/hal-00675936/PDF/morcrette\_latin2012.pdf},
      url = {http://hal.archives-ouvertes.fr/hal-00675936}
    }
  • [2012,inproceedings] bibtex Go to document
    A. Genitrini, O. Bodini, and F. Peschanski, "Enumeration and Random Generation of Concurrent Computations," in DMTCS, Canada, 2012.
    @INPROCEEDINGS{genitrini:hal-00699964, author = {Genitrini, Antoine and Bodini, Olivier and Peschanski, Fr{\'e}d{\'e}ric},
      title = {{Enumeration and Random Generation of Concurrent Computations}},
      booktitle = {{DMTCS}},
      year = {2012},
      pages = {to appear},
      address = {Canada},
      affiliation = {Laboratoire d'Informatique de Paris 6 - LIP6 , Laboratoire d'informatique de Paris-nord - LIPN},
      audience = {internationale },
      collaboration = {APR, CALIN },
      hal_id = {hal-00699964},
      language = {Anglais},
      url = {http://hal.archives-ouvertes.fr/hal-00699964}
    }
  • [2012,article] bibtex Go to document
    F. Bassino, J. David, and C. Nicaud, "Average Case Analysis of Moore’s State Minimization Algorithm," Algorithmica, vol. 63, iss. 1, pp. 509-531, 2012.
    @ARTICLE{bassino:hal-00619784, author = {Bassino, Fr{\'e}d{\'e}rique and David, Julien and Nicaud, Cyril},
      title = {{Average Case Analysis of Moore's State Minimization Algorithm}},
      journal = {{Algorithmica}},
      year = {2012},
      volume = {63},
      pages = {509-531},
      number = {1},
      owner = {Yawn},
      timestamp = {2013.03.11},
      url = {http://hal.inria.fr/hal-00619784}
    }
  • [2012,inproceedings] bibtex Go to document
    J. Du Boisberranger, D. Gardy, and Y. Ponty, "The weighted words collector," in AOFA – 23rd International Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms – 2012, Montreal, Canada, 2012.
    @INPROCEEDINGS{duboisberranger:hal-00666399, author = {Du Boisberranger, J{\'e}r{\'e}mie and Gardy, Dani{\`e}le and Ponty, Yann},
      title = {{The weighted words collector}},
      booktitle = {{AOFA - 23rd International Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms - 2012}},
      year = {2012},
      pages = {TBA},
      address = {Montreal, Canada},
      abstract = {{Motivated by applications in bioinformatics, we consider the word collector problem, i.e. the expected number of calls to a random weighted generator of words of length $n$ before the full collection is obtained. The originality of this instance of the non-uniform coupon collector lies in the, potentially large, multiplicity of the words/coupons of a given probability/composition. We obtain a general theorem that gives an asymptotic equivalent for the expected waiting time of a general version of the Coupon Collector. This theorem is especially well-suited for classes of coupons featuring high multiplicities. Its application to a given language essentially necessitates some knowledge on the number of words of a given composition/probability. We illustrate the application of our theorem, in a step-by-step fashion, on three exemplary languages, revealing asymptotic regimes in $\Theta(\mu(n)\cdot n)$ and $\Theta(\mu(n)\cdot \log n)$, where $\mu(n)$ is the sum of weights over words of length $n$.}},
      affiliation = {Parall{\'e}lisme, R{\'e}seaux, Syst{\`e}mes d'information, Mod{\'e}lisation - PRISM , Laboratoire d'informatique de l'{\'e}cole polytechnique - LIX , AMIB - INRIA Saclay - Ile de France},
      audience = {internationale },
      hal_id = {hal-00666399},
      keywords = {Coupon Collector Problem;Waiting Time;Random Generation;Weighted Context-free Languages},
      language = {Anglais},
      pdf = {http://hal.inria.fr/hal-00666399/PDF/WordCollector-Daniele-Jeremie-Yann-2012.pdf},
      url = {http://hal.inria.fr/hal-00666399}
    }
  • [2012,inproceedings] bibtex Go to document
    F. Bassino, M. Bouvel, A. Pierrot, C. Pivoteau, and D. Rossin, "Combinatorial specification of permutation classes," in FPSAC 2012 (24th International Conference on Formal Power Series and Algebraic Combinatorics), Nagoya, Japon, 2012, pp. 781-792.
    @INPROCEEDINGS{bassino:hal-00685023, author = {Bassino, Fr{\'e}d{\'e}rique and Bouvel, Mathilde and Pierrot, Adeline and Pivoteau, Carine and Rossin, Dominique},
      title = {{Combinatorial specification of permutation classes}},
      booktitle = {{FPSAC 2012 (24th International Conference on Formal Power Series and Algebraic Combinatorics)}},
      year = {2012},
      volume = {AR},
      pages = {781 - 792},
      address = {Nagoya, Japon},
      keywords = {permutation classes, excluded patterns, substitution decomposition, simple permutations, generating functions, combinatorial specification, random generation},
      owner = {Yawn},
      timestamp = {2013.03.11},
      url = {http://hal.inria.fr/hal-00685023}
    }
  • [2012,inproceedings] bibtex Go to document
    O. Aitmous, F. Bassino, and C. Nicaud, "An Efficient Linear Pseudo-Minimization Algorithm for Aho-Corasick Automata," in 23st Annual Symposium on Combinatorial Pattern Matching (CPM’12), Finlande, 2012, pp. 110-123.
    @INPROCEEDINGS{aitmous:hal-00793395, author = {Aitmous, Omar and Bassino, Fr{\'e}d{\'e}rique and Nicaud, Cyril},
      title = {{An Efficient Linear Pseudo-Minimization Algorithm for Aho-Corasick Automata}},
      booktitle = {{23st Annual Symposium on Combinatorial Pattern Matching (CPM'12)}},
      year = {2012},
      volume = {7354},
      pages = {110-123},
      address = {Finlande},
      owner = {Yawn},
      timestamp = {2013.03.11},
      url = {http://hal.inria.fr/hal-00793395}
    }
  • [2012,article] bibtex Go to document
    F. Bassino, A. Martino, C. Nicaud, E. Ventura, and P. Weil, "Statistical properties of subgroups of free groups," Random Structures and Algorithms, 2012.
    @ARTICLE{bassino:hal-00450218, author = {Bassino, Fr{\'e}d{\'e}rique and Martino, Armando and Nicaud, Cyril and Ventura, Enric and Weil, Pascal},
      title = {{Statistical properties of subgroups of free groups}},
      journal = {{Random Structures and Algorithms}},
      year = {2012},
      note = {page : to appear},
      keywords = {subgroups of free groups; finite group presentations; statistical properties; Stallings graphs; partial injections; malnormality},
      owner = {Yawn},
      timestamp = {2013.03.11},
      url = {http://hal.inria.fr/hal-00450218}
    }
  • [2012,article] bibtex Go to document
    C. Banderier and P. Hitczenko, "Enumeration and asymptotics of restricted compositions having the same number of parts," Discrete Applied Mathematics, pp. 1-13, 2012.
    @ARTICLE{banderier:hal-00664192, author = {Banderier, Cyril and Hitczenko, Pawel},
      title = {{Enumeration and asymptotics of restricted compositions having the same number of parts}},
      journal = {Discrete Applied Mathematics},
      year = {2012},
      pages = {1-13},
      note = {CALIN CALIN },
      abstract = {{We study pairs and m-tuples of compositions of a positive integer n with parts restricted to a subset P of positive integers. We obtain some exact enumeration results for the number of tuples of such compositions having the same number of parts. Under the uniform probability model, we obtain the asymptotics for the probability that two or, more generally, m randomly and independently chosen compositions of n have the same number of parts. For a large class of compositions, we show how a nice interplay between complex analysis and probability theory allows to get full asymptotics for this probability. Our results extend an earlier work of B{\'o}na and Knopfmacher. While we restrict our attention to compositions, our approach is also of interest for tuples of other combinatorial structures having the same number of parts.}},
      affiliation = {Laboratoire d'informatique de Paris-nord - LIPN , Departments of Mathematics and Computer Science},
      audience = {internationale },
      doi = {10.1016/j.dam.2011.12.011 },
      hal_id = {hal-00664192},
      keywords = {Integer composition; Pairs of combinatorial structures; Local limit theorem; Asymptotics of D-finite sequences; Diagonal of algebraic generating function},
      language = {Anglais},
      pdf = {http://hal.archives-ouvertes.fr/hal-00664192/PDF/BaHi.pdf},
      url = {http://hal.archives-ouvertes.fr/hal-00664192}
    }
  • [2012,article] bibtex Go to document
    F. Bassino, A. Martino, C. Nicaud, E. Ventura, and P. Weil, "Statistical properties of subgroups of free groups," Random Structures and Algorithms, 2012.
    @ARTICLE{bassino:hal-00450218, author = {Bassino, Fr{\'e}d{\'e}rique and Martino, Armando and Nicaud, Cyril and Ventura, Enric and Weil, Pascal},
      title = {{Statistical properties of subgroups of free groups}},
      journal = {Random Structures and Algorithms},
      year = {2012},
      pages = {to appear},
      abstract = {{The usual way to investigate the statistical properties of finitely generated subgroups of free groups, and of finite presentations of groups, is based on the so-called word-based distribution: subgroups are generated (finite presentations are determined) by randomly chosen k-tuples of reduced words, whose maximal length is allowed to tend to infinity. In this paper we adopt a different, though equally natural point of view: we investigate the statistical properties of the same objects, but with respect to the so-called graph-based distribution, recently introduced by Bassino, Nicaud and Weil. Here, subgroups (and finite presentations) are determined by randomly chosen Stallings graphs whose number of vertices tends to infinity. Our results show that these two distributions behave quite differently from each other, shedding a new light on which properties of finitely generated subgroups can be considered frequent or rare. For example, we show that malnormal subgroups of a free group are negligible in the graph-based distribution, while they are exponentially generic in the word-based distribution. Quite surprisingly, a random finite presentation generically presents the trivial group in this new distribution, while in the classical one it is known to generically present an infinite hyperbolic group.}},
      affiliation = {Laboratoire d'informatique de Paris-nord - LIPN , School of Mathematics , Laboratoire d'Informatique Gaspard-Monge - LIGM , Department of Applied Mathematics III , Laboratoire Bordelais de Recherche en Informatique - LaBRI},
      audience = {internationale },
      hal_id = {hal-00450218},
      keywords = {subgroups of free groups; finite group presentations; statistical properties; Stallings graphs; partial injections; malnormality},
      language = {Anglais},
      pdf = {http://hal.archives-ouvertes.fr/hal-00450218/PDF/BMNVW.pdf},
      url = {http://hal.archives-ouvertes.fr/hal-00450218}
    }
  • [2012,article] bibtex Go to document
    P. Clote, Y. Ponty, and J. Steyaert, "Expected distance between terminal nucleotides of RNA secondary structures.," Journal of Mathematical Biology, vol. 65, iss. 3, pp. 581-99, 2012.
    @ARTICLE{clote:inria-00619921, author = {Clote, Peter and Ponty, Yann and Steyaert, Jean-Marc},
      title = {{Expected distance between terminal nucleotides of RNA secondary structures.}},
      journal = {Journal of Mathematical Biology},
      year = {2012},
      volume = {65},
      pages = {581-99},
      number = {3 },
      month = Sep, note = {Digiteo Foundation and National Science Foundation grants DMS- 0817971, DBI-0543506 and DMS-1016618. },
      abstract = {{In "The ends of a large RNA molecule are necessarily close", Yoffe et al. (Nucleic Acids Res 39(1):292-299, 2011) used the programs RNAfold [resp. RNAsubopt] from Vienna RNA Package to calculate the distance between 5' and 3' ends of the minimum free energy secondary structure [resp. thermal equilibrium structures] of viral and random RNA sequences. Here, the 5'-3' distance is defined to be the length of the shortest path from 5' node to 3' node in the undirected graph, whose edge set consists of edges {i, i + 1} corresponding to covalent backbone bonds and of edges {i, j} corresponding to canonical base pairs. From repeated simulations and using a heuristic theoretical argument, Yoffe et al. conclude that the 5'-3' distance is less than a fixed constant, independent of RNA sequence length. In this paper, we provide a rigorous, mathematical framework to study the expected distance from 5' to 3' ends of an RNA sequence. We present recurrence relations that precisely define the expected distance from 5' to 3' ends of an RNA sequence, both for the Turner nearest neighbor energy model, as well as for a simple homopolymer model first defined by Stein and Waterman. We implement dynamic programming algorithms to compute (rather than approximate by repeated application of Vienna RNA Package) the expected distance between 5' and 3' ends of a given RNA sequence, with respect to the Turner energy model. Using methods of analytical combinatorics, that depend on complex analysis, we prove that the asymptotic expected 5'-3' distance of length n homopolymers is approximately equal to the constant 5.47211, while the asymptotic distance is 6.771096 if hairpins have a minimum of 3 unpaired bases and the probability that any two positions can form a base pair is 1/4. Finally, we analyze the 5'-3' distance for secondary structures from the STRAND database, and conclude that the 5'-3' distance is correlated with RNA sequence length.}},
      affiliation = {Laboratoire d'informatique de l'{\'e}cole polytechnique - LIX , Department of Biology , AMIB - INRIA Saclay - Ile de France},
      audience = {internationale },
      doi = {10.1007/s00285-011-0467-8 },
      hal_id = {inria-00619921},
      language = {Anglais},
      pdf = {http://hal.inria.fr/inria-00619921/PDF/paper.pdf},
      publisher = {Springer},
      url = {http://hal.inria.fr/inria-00619921}
    }
  • [2012,inproceedings] bibtex Go to document
    F. Bassino, J. David, and A. Sportiello, "Asymptotic enumeration of Minimal Automata," in STACS’12 (29th Symposium on Theoretical Aspects of Computer Science), Paris, France, 2012, pp. 88-99.
    @INPROCEEDINGS{bassino:hal-00678203, author = {Bassino, Fr{\'e}d{\'e}rique and David, Julien and Sportiello, Andrea},
      title = {{Asymptotic enumeration of Minimal Automata}},
      booktitle = {{STACS'12 (29th Symposium on Theoretical Aspects of Computer Science)}},
      year = {2012},
      editor = {Christoph D{\"u}rr, Thomas Wilke},
      volume = {14},
      pages = {88-99},
      address = {Paris, France},
      month = Mar, publisher = {LIPIcs},
      keywords = {minimal automata, regular languages, enumeration of random structures},
      owner = {Yawn},
      timestamp = {2013.03.11},
      url = {http://hal.inria.fr/hal-00678203}
    }
  • [2012,inproceedings] bibtex Go to document
    F. Bassino, C. Nicaud, and P. Weil, "Generic properties of random subgroups of a free group for general distributions," in Proceedings of Analysis of Algorithms (AofA 2012), Canada, 2012, pp. 155-166.
    @INPROCEEDINGS{bassino:hal-00687981, author = {Bassino, Fr{\'e}d{\'e}rique and Nicaud, Cyril and Weil, Pascal},
      title = {{Generic properties of random subgroups of a free group for general distributions}},
      booktitle = {{Proceedings of Analysis of Algorithms (AofA 2012)}},
      year = {2012},
      volume = {AQ},
      series = {Discrete Mathematics and Theoretical Computer Science },
      pages = {155-166},
      address = {Canada},
      abstract = {{We consider a generalization of the uniform word-based distribution for finitely generated subgroups of a free group. In our setting, the number of generators is not fixed, the length of each generator is determined by a random variable with some simple constraints and the distribution of words of a fixed length is specified by a Markov process. We show by probabilistic arguments that under rather relaxed assumptions, the good properties of the uniform word-based distribution are preserved: generically (but maybe not exponentially generically), the tuple we pick is a basis of the subgroup it generates, this subgroup is malnormal and the group presentation defined by this tuple satisfies a small cancellation condition.}},
      affiliation = {Laboratoire d'informatique de Paris-nord - LIPN , Laboratoire d'Informatique Gaspard-Monge - LIGM , Laboratoire Bordelais de Recherche en Informatique - LaBRI},
      audience = {internationale },
      hal_id = {hal-00687981},
      language = {Anglais},
      pdf = {http://hal.archives-ouvertes.fr/hal-00687981/PDF/BNW-AofA.pdf},
      url = {http://hal.archives-ouvertes.fr/hal-00687981}
    }
  • [2012,article] bibtex Go to document
    S. Behrens, C. Nicaud, and P. Nicodème, "An Automaton Approach for Waiting Times in DNA Evolution," Journal of Computational Biology, vol. 19, iss. 5, pp. 550-562, 2012.
    @ARTICLE{behrens:hal-00793413, author = {Behrens, Sarah and Nicaud, Cyril and Nicod{\`e}me, Pierre},
      title = {{An Automaton Approach for Waiting Times in DNA Evolution}},
      journal = {{Journal of Computational Biology}},
      year = {2012},
      volume = {19},
      pages = {550-562},
      number = {5},
      owner = {Yawn},
      timestamp = {2013.03.11},
      url = {http://hal.inria.fr/hal-00793413}
    }
  • [2011,inproceedings] bibtex Go to document
    G. Giakkoupis and N. Schabanel, "Le rôle de la dimension dans la recherche de chemins optimaux dans les petits mondes," in 13es Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel), Cap Estérel, France, 2011, p. 4.
    @INPROCEEDINGS{giakkoupis:hal-00587955, author = {Giakkoupis, George and Schabanel, Nicolas},
      title = {{Le r{\^o}le de la dimension dans la recherche de chemins optimaux dans les petits mondes}},
      booktitle = {{13es Rencontres Francophones sur les Aspects Algorithmiques de T{\'e}l{\'e}communications (AlgoTel)}},
      year = {2011},
      editor = {Ducourthial, Bertrand and Felber, Pascal},
      volume = {13},
      pages = {4 pages},
      address = {Cap Est{\'e}rel, France},
      keywords = {small worlds; social networks; peer-to-peer networks ; decentralized search; optimal paths},
      owner = {Yawn},
      timestamp = {2013.03.11},
      url = {http://hal.inria.fr/hal-00587955}
    }
  • [2011,inproceedings] bibtex Go to document
    Y. Ponty and C. Saule, "A Combinatorial Framework for Designing (Pseudoknotted) RNA Algorithms," in 11th Workshop on Algorithms in Bioinformatics (WABI’11), Saarbrucken, Allemagne, 2011.
    @INPROCEEDINGS{ponty:inria-00601060, author = {Ponty, Yann and Saule, C{\'e}dric},
      title = {{A Combinatorial Framework for Designing (Pseudoknotted) RNA Algorithms}},
      booktitle = {{11th Workshop on Algorithms in Bioinformatics (WABI'11)}},
      year = {2011},
      address = {Saarbrucken, Allemagne},
      abstract = {{We extend an hypergraph representation, introduced by Finkelstein and Roytberg, to unify dynamic programming algorithms in the context of RNA folding with pseudoknots. Classic applications of RNA dynamic programming energy minimization, partition function, base-pair probabilities\ldots) are reformulated within this framework, giving rise to very simple algorithms. This reformulation allows one to conceptually detach the conformation space/energy model -- captured by the hypergraph model -- from the specific application, assuming unambiguity of the decomposition. To ensure the latter property, we propose a new combinatorial methodology based on generating functions. We extend the set of generic applications by proposing an exact algorithm for extracting generalized moments in weighted distribution, generalizing a prior contribution by Miklos and al. Finally, we illustrate our full-fledged programme on three exemplary conformation spaces (secondary structures, Akutsu's simple type pseudoknots and kissing hairpins). This readily gives sets of algorithms that are either novel or have complexity comparable to classic implementations for minimization and Boltzmann ensemble applications of dynamic programming.}},
      affiliation = {AMIB - INRIA Saclay - Ile de France , Laboratoire d'informatique de l'{\'e}cole polytechnique - LIX , Laboratoire de Recherche en Informatique - LRI , Institut de Recherche en Immunologie et en Canc{\'e}rologie - IRIC},
      audience = {internationale },
      hal_id = {inria-00601060},
      language = {Anglais},
      pdf = {http://hal.inria.fr/inria-00601060/PDF/BoltzmannEnsembleWithPK.pdf},
      url = {http://hal.inria.fr/inria-00601060}
    }
  • [2011,article] bibtex Go to document
    E. Bertin, G. Beslon, O. Gandrillon, S. Grauwin, P. Jensen, and N. Schabanel, "Les complexités : point de vue d’un institut des systèmes complexes," Hermes, iss. 60, pp. 145-150, 2011.
    @ARTICLE{bertin:hal-00744520, author = {Bertin, Eric and Beslon, Guillaume and Gandrillon, Olivier and Grauwin, S{\'e}bastian and Jensen, Pablo and Schabanel, Nicolas},
      title = {{Les complexit{\'e}s : point de vue d'un institut des syst{\`e}mes complexes}},
      journal = {{Hermes}},
      year = {2011},
      pages = {145-150},
      number = {60},
      month = Jun, owner = {Yawn},
      timestamp = {2013.03.11},
      url = {http://hal.inria.fr/hal-00744520}
    }
  • [2011,inproceedings] bibtex Go to document
    F. Pin, A. Busic, and B. Gaujal, "Acceleration of perfect sampling by skipping events," in VALUETOOLS ’11 – 5th International ICST Conference on Performance Evaluation Methodologies and Tools, Paris, France, 2011, pp. 207-216.
    @INPROCEEDINGS{pin:hal-00788799, author = {Pin, Furcy and Busic, Ana and Gaujal, Bruno},
      title = {{Acceleration of perfect sampling by skipping events}},
      booktitle = {{VALUETOOLS '11 - 5th International ICST Conference on Performance Evaluation Methodologies and Tools}},
      year = {2011},
      pages = {207-216},
      address = {Paris, France},
      publisher = {ICST},
      owner = {Yawn},
      timestamp = {2013.03.11},
      url = {http://hal.inria.fr/hal-00788799}
    }
  • [2011,inproceedings] bibtex Go to document
    O. Bodini, O. Roussel, and M. Soria, "Boltzmann samplers for first-order differential specifications," in LAGOS 09 – V Latin – American Algorithms, Graphs and Optimization Symposium, Gramado, Brésil, 2011, p. 1.
    @INPROCEEDINGS{bodini:hal-00641072, author = {Bodini, Olivier and Roussel, Olivier and Soria, Michele},
      title = {{Boltzmann samplers for first-order differential specifications}},
      booktitle = {{LAGOS 09 - V Latin - American Algorithms, Graphs and Optimization Symposium}},
      year = {2011},
      pages = {1},
      address = {Gramado, Br{\'e}sil},
      note = {15 pages},
      owner = {Yawn},
      timestamp = {2013.03.11},
      url = {http://hal.inria.fr/hal-00641072}
    }
  • [2011,article] bibtex Go to document
    M. H. Albert, M. D. Atkinson, M. Bouvel, A. Claesson, and M. Dukes, "On the inverse image of pattern classes under bubble sort," Journal of Combinatorics, vol. 2, iss. 2, pp. 231-244, 2011.
    @ARTICLE{albert:hal-00525425, author = {Albert, Michael H. and Atkinson, M. D. and Bouvel, Mathilde and Claesson, Anders and Dukes, Mark},
      title = {{On the inverse image of pattern classes under bubble sort}},
      journal = {{Journal of Combinatorics}},
      year = {2011},
      volume = {2},
      pages = {231-244},
      number = {2},
      note = {11 pages},
      owner = {Yawn},
      timestamp = {2013.03.11},
      url = {http://hal.inria.fr/hal-00525425}
    }
  • [2011,inproceedings] bibtex Go to document
    P. Flajolet, M. Pelletier, and M. Soria, "On Buffon Machines and Numbers," in Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), San Francisco, États-Unis, 2011, p. pp. 172-183.
    @INPROCEEDINGS{flajolet:hal-00548904, author = {Flajolet, Philippe and Pelletier, Maryse and Soria, Mich{\`e}le},
      title = {{On Buffon Machines and Numbers}},
      booktitle = {{Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)}},
      year = {2011},
      pages = {pp. 172--183},
      address = {San Francisco, {\'E}tats-Unis},
      note = {Largely revised version with references and figures added. 12 pages. },
      abstract = {{The well-know needle experiment of Buffon can be regarded as an analog (i.e., continuous) device that stochastically "computes" the number 2/pi \~ 0.63661, which is the experiment's probability of success. Generalizing the experiment and simplifying the computational framework, we consider probability distributions, which can be produced perfectly, from a discrete source of unbiased coin flips. We describe and analyse a few simple Buffon machines that generate geometric, Poisson, and logarithmic-series distributions. We provide human-accessible Buffon machines, which require a dozen coin flips or less, on average, and produce experiments whose probabilities of success are expressible in terms of numbers such as, exp(-1), log 2, sqrt(3), cos(1/4), aeta(5). Generally, we develop a collection of constructions based on simple probabilistic mechanisms that enable one to design Buffon experiments involving compositions of exponentials and logarithms, polylogarithms, direct and inverse trigonometric functions, algebraic and hypergeometric functions, as well as functions defined by integrals, such as the Gaussian error function.}},
      affiliation = {ALGORITHMS - INRIA Rocquencourt , Laboratoire d'Informatique de Paris 6 - LIP6},
      audience = {internationale },
      collaboration = {lip6; inria },
      hal_id = {hal-00548904},
      language = {Anglais},
      pdf = {http://hal.archives-ouvertes.fr/hal-00548904/PDF/0906.5560v2.pdf},
      url = {http://hal.archives-ouvertes.fr/hal-00548904}
    }
  • [2011,inproceedings] bibtex Go to document
    P. Héam and C. Nicaud, "Seed, an Easy-to-Use Random Generator of Recursive Data Structures for Testing," in 4th IEEE International Conference on Software Testing, Verification and Validation (ICST’11), Berlin, Allemagne, 2011, pp. 60-69.
    @INPROCEEDINGS{heam:hal-00620373, author = {H{\'e}am, Pierre-Cyrille and Nicaud, Cyril},
      title = {{Seed, an Easy-to-Use Random Generator of Recursive Data Structures for Testing}},
      booktitle = {{4th IEEE International Conference on Software Testing, Verification and Validation (ICST'11)}},
      year = {2011},
      pages = {60 - 69},
      address = {Berlin, Allemagne},
      publisher = {IEEE},
      doi = {10.1109/ICST.2011.31},
      owner = {Yawn},
      timestamp = {2013.03.11},
      url = {http://hal.inria.fr/hal-00620373}
    }
  • [2011,techreport] bibtex Go to document
    A. Wieczorek, A. Busic, and E. Hyon, "Critical level policies in lost sales inventory systems with different demand classes," INRIA, Rapport de recherche RR-7732, 2011.
    @TECHREPORT{wieczorek:inria-00620243, author = {Wieczorek, Aleksander and Busic, Ana and Hyon, Emmanuel},
      title = {{Critical level policies in lost sales inventory systems with different demand classes}},
      institution = {INRIA},
      year = {2011},
      type = {Rapport de recherche},
      number = {RR-7732},
      month = Sep, keywords = {Markov decision process; Critical level policies; Inventory systems},
      owner = {Yawn},
      timestamp = {2013.03.11},
      url = {http://hal.inria.fr/inria-00620243}
    }
  • [2011,inproceedings] bibtex Go to document
    S. Janssen, Y. Ponty, B. Raman, S. Sheikh, J. Steyaert, and P. Clote, "Investigating the RFAM paradox: The pseudoknot explanation," in Fifth Indo-French Bioinformatics Meeting, Hyderabad, Inde, 2011.
    @INPROCEEDINGS{janssen:hal-00585647, author = {Janssen, Stefan and Ponty, Yann and Raman, Balaji and Sheikh, Saad and Steyaert, Jean-Marc and Clote, Peter},
      title = {{Investigating the RFAM paradox: The pseudoknot explanation}},
      booktitle = {{Fifth Indo-French Bioinformatics Meeting}},
      year = {2011},
      address = {Hyderabad, Inde},
      month = Mar, note = {Short abstract},
      owner = {Yawn},
      timestamp = {2013.03.11},
      url = {http://hal.inria.fr/hal-00585647}
    }
  • [2011,article] bibtex Go to document
    F. Bassino, M. Bouvel, and D. Rossin, "Enumeration of Pin-Permutations," Electronic Journal of Combinatorics, vol. 18, iss. 1, p. 57, 2011.
    @ARTICLE{bassino:hal-00348664, author = {Bassino, Fr{\'e}d{\'e}rique and Bouvel, Mathilde and Rossin, Dominique},
      title = {{Enumeration of Pin-Permutations}},
      journal = {{Electronic Journal of Combinatorics}},
      year = {2011},
      volume = {18},
      pages = {P57},
      number = {1},
      note = {39 pages},
      keywords = {Permutation ; Generating function ; Permutation Pattern},
      owner = {Yawn},
      timestamp = {2013.03.11},
      url = {http://hal.inria.fr/hal-00348664}
    }
  • [2011,article] bibtex Go to document
    M. Bouvel, C. Chauve, M. Mishna, and D. Rossin, "Average-case analysis of perfect sorting by reversals," Discrete Mathematics, Algorithms and Applications, vol. 3, iss. 3, pp. 369-392, 2011.
    @ARTICLE{bouvel:hal-00649761, author = {Bouvel, Mathilde and Chauve, C{\'e}dric and Mishna, Marni and Rossin, Dominique},
      title = {{Average-case analysis of perfect sorting by reversals}},
      journal = {Discrete Mathematics, Algorithms and Applications},
      year = {2011},
      volume = {3},
      pages = {369-392},
      number = {3 },
      abstract = {{Perfect sorting by reversals, a problem originating in computational genomics, is the process of sorting a signed permutation to either the identity or to the reversed identity permutation, by a sequence of reversals that do not break any common interval. B{\'e}rard et al. (2007) make use of strong interval trees to describe an algorithm for sorting signed permutations by reversals. Combinatorial properties of this family of trees are essential to the algorithm analysis. Here, we use the expected value of certain tree parameters to prove that the average run-time of the algorithm is at worst, polynomial, and additionally, for sufficiently long permutations, the sorting algorithm runs in polynomial time with probability one. Furthermore, our analysis of the subclass of commuting scenarios yields precise results on the average length of a reversal, and the average number of reversals. A preliminary version of this work appeared in the proceedings of Combinatorial Pattern Matching (CPM) 2009, Lectures Notes in Computer Science, vol. 5577, pp. 314--325, Springer.}},
      affiliation = {Laboratoire Bordelais de Recherche en Informatique - LaBRI , Department of Mathematics , Laboratoire d'informatique de l'{\'e}cole polytechnique - LIX},
      audience = {internationale },
      doi = {10.1142/S1793830911001280 },
      hal_id = {hal-00649761},
      keywords = {Algorithm analysis ; genome rearrangements ; tree parameters ; simple permutations},
      language = {Anglais},
      pdf = {http://hal.archives-ouvertes.fr/hal-00649761/PDF/BoChMiRo\_HAL.pdf},
      url = {http://hal.archives-ouvertes.fr/hal-00649761}
    }
  • [2011,inproceedings] bibtex Go to document
    C. Banderier and P. Nicodeme, "Constant time estimation of ranking statistics by analytic combinatorics," in Statistical Methods for Post-Genomic Data, Paris, France, 2011, p. i.
    @INPROCEEDINGS{banderier:hal-00567091, author = {Banderier, Cyril and Nicodeme, Pierre},
      title = {{Constant time estimation of ranking statistics by analytic combinatorics}},
      booktitle = {{Statistical Methods for Post-Genomic Data}},
      year = {2011},
      pages = {no page numbering},
      address = {Paris, France},
      month = Jan, keywords = {ranking statictics; analytic combinatorics; Rayleigh function},
      owner = {Yawn},
      timestamp = {2013.03.11},
      url = {http://hal.inria.fr/hal-00567091}
    }
  • [2011,article] bibtex Go to document
    J. Waldispühl and Y. Ponty, "An unbiased adaptive sampling algorithm for the exploration of RNA mutational landscapes under evolutionary pressure.," Journal of Computational Biology, vol. 18, iss. 11, pp. 1465-79, 2011.
    @ARTICLE{waldispuhl:hal-00681928, author = {Waldisp{\"u}hl, J{\'e}r{\^o}me and Ponty, Yann},
      title = {{An unbiased adaptive sampling algorithm for the exploration of RNA mutational landscapes under evolutionary pressure.}},
      journal = {Journal of Computational Biology},
      year = {2011},
      volume = {18},
      pages = {1465-79},
      number = {11 },
      month = Nov, abstract = {{The analysis of the relationship between sequences and structures (i.e., how mutations affect structures and reciprocally how structures influence mutations) is essential to decipher the principles driving molecular evolution, to infer the origins of genetic diseases, and to develop bioengineering applications such as the design of artificial molecules. Because their structures can be predicted from the sequence data only, RNA molecules provide a good framework to study this sequence-structure relationship. We recently introduced a suite of algorithms called RNAmutants which allows a complete exploration of RNA sequence-structure maps in polynomial time and space. Formally, RNAmutants takes an input sequence (or seed) to compute the Boltzmann-weighted ensembles of mutants with exactly k mutations, and sample mutations from these ensembles. However, this approach suffers from major limitations. Indeed, since the Boltzmann probabilities of the mutations depend of the free energy of the structures, RNAmutants has difficulties to sample mutant sequences with low G+C-contents. In this article, we introduce an unbiased adaptive sampling algorithm that enables RNAmutants to sample regions of the mutational landscape poorly covered by classical algorithms. We applied these methods to sample mutations with low G+C-contents. These adaptive sampling techniques can be easily adapted to explore other regions of the sequence and structural landscapes which are difficult to sample. Importantly, these algorithms come at a minimal computational cost. We demonstrate the insights offered by these techniques on studies of complete RNA sequence structures maps of sizes up to 40 nucleotides. Our results indicate that the G+C-content has a strong influence on the size and shape of the evolutionary accessible sequence and structural spaces. In particular, we show that low G+C-contents favor the apparition of internal loops and thus possibly the synthesis of tertiary structure motifs. On the other hand, high G+C-contents significantly reduce the size of the evolutionary accessible mutational landscapes.}},
      affiliation = {McGill University , Laboratoire d'informatique de l'{\'e}cole polytechnique - LIX , AMIB - INRIA Saclay - Ile de France},
      audience = {internationale },
      doi = {10.1089/cmb.2011.0181 },
      hal_id = {hal-00681928},
      language = {Anglais},
      publisher = {Mary Ann Liebert},
      url = {http://hal.inria.fr/hal-00681928}
    }
  • [2011,inproceedings] bibtex Go to document
    J. Waldispühl and Y. Ponty, "An unbiased adaptive sampling algorithm for the exploration of RNA mutational landscapes under evolutionary pressure," in Research in Computational Molecular Biology, Vancouver, Canada, 2011, pp. 501-515.
    @INPROCEEDINGS{waldispuhl:hal-00546847, author = {Waldisp{\"u}hl, J{\'e}r{\^o}me and Ponty, Yann},
      title = {{An unbiased adaptive sampling algorithm for the exploration of RNA mutational landscapes under evolutionary pressure}},
      booktitle = {{Research in Computational Molecular Biology}},
      year = {2011},
      editor = {Bafna, Vineet and Sahinalp, S. },
      volume = {6577},
      series = {Lecture Notes in Computer Science },
      pages = {501-515},
      address = {Vancouver, Canada},
      publisher = {Springer Berlin / Heidelberg},
      abstract = {{The analysis of the relationship between sequences and structures (i.e. how mutations aect structures and reciprocally how structures in uence mutations) is essential to decipher the principles driving molecular evolution, to infer the origins of genetic diseases or to develop bioengineering applications such as the design of articial molecules. Because their structures can be predicted from the sequence data only, RNA molecules provide a good framework to study this sequence-structure relationship. We recently introduced a suite of algorithms called RNAmutants which allows, for the rst time, a complete exploration of RNA sequence-structure maps in polynomial time and space. Formally, RNAmutants takes an input sequence (or seed) to compute the Boltzmann weighted ensembles of mutants with exactly k mutations, and sample mutations from these ensembles. However, this approach suers from major limitations. Indeed, since the Boltzmann probabilities of the mutations depend of the free energy of the structures, RNAmutants has diculties to sample mutant sequences with low G+C-contents. In this paper we introduce a novel unbiased adaptive sampling algorithm that enables RNAmutants to sample regions of the mutational landscape poorly covered by classical algorithms. We applied these methods to sample mutations with low G+C-contents. These adaptive sampling techniques can be easily adapted to explore other regions of the sequence and structural landscapes which are dif- cult to sample. Importantly, these algorithms come at a minimal computational cost. We demonstrate the insights oered by these techniques on studies of complete RNA sequence structures maps of sizes up to 40 nucleotides. Our results indicate that the G+C-content has a strong in uence on the size and shape of the evolutionary accessible sequence and structural spaces. In particular, we show that low G+C-contents favor the apparition of internal loops and thus possibly the synthesis of tertiary structure motifs. On the other hand, high G+C-contents signicantly reduce the size of the evolutionary accessible mutational landscapes.}},
      affiliation = {McGill University , AMIB - INRIA Saclay - Ile de France , Laboratoire d'informatique de l'{\'e}cole polytechnique - LIX},
      audience = {internationale },
      doi = {10.1007/978-3-642-20036-6\_45 },
      hal_id = {hal-00546847},
      language = {Anglais},
      pdf = {http://hal.archives-ouvertes.fr/hal-00546847/PDF/paper.pdf},
      url = {http://hal.archives-ouvertes.fr/hal-00546847}
    }
  • [2011,article] bibtex Go to document
    B. Chauvin, B. Salvy, M. Soria, and B. Vallee, "Philippe Flajolet, le fondateur de la combinatoire analytique," La gazette des mathématiciens, vol. 129, pp. 113-114, 2011.
    @ARTICLE{chauvin:hal-00680928, author = {Chauvin, Brigitte and Salvy, Bruno and Soria, Mich{\`e}le and Vallee, Brigitte},
      title = {{Philippe Flajolet, le fondateur de la combinatoire analytique}},
      journal = {{La gazette des math{\'e}maticiens}},
      year = {2011},
      volume = {129},
      pages = {113-114},
      month = Jul, owner = {Yawn},
      timestamp = {2013.03.11},
      url = {http://hal.inria.fr/hal-00680928}
    }
  • [2011,article] bibtex Go to document
    T. Zuliani, J. David, S. Bercegeay, M. Pandolfino, I. Rodde-Astier, A. Khammari, C. Coissac, B. Delorme, S. Saïagh, and B. Dréno, "Value of large scale expansion of tumor infiltrating lymphocytes in a compartmentalised gas-permeable bag: interests for adoptive immunotherapy.," Journal of Translational Medicine, vol. 9, iss. 1, p. 63, 2011.
    @ARTICLE{zuliani:inserm-00663657, author = {Zuliani, Thomas and David, Julien and Bercegeay, Sylvain and Pandolfino, Marie-Christine and Rodde-Astier, Isabelle and Khammari, Amir and Coissac, C{\'e}cile and Delorme, Bruno and Sa{\"\i}agh, Soraya and Dr{\'e}no, Brigitte},
      title = {{Value of large scale expansion of tumor infiltrating lymphocytes in a compartmentalised gas-permeable bag: interests for adoptive immunotherapy.}},
      journal = {{Journal of Translational Medicine}},
      year = {2011},
      volume = {9},
      pages = {63},
      number = {1},
      doi = {10.1186/1479-5876-9-63},
      owner = {Yawn},
      timestamp = {2013.03.11},
      url = {http://hal.inria.fr/inserm-00663657}
    }
  • [2010,article] bibtex Go to document
    A. Denise, Y. Ponty, and M. Termier, "Controlled non uniform random generation of decomposable structures," Journal of Theoretical Computer Science (TCS), vol. 411, iss. 40-42, pp. 3527-3552, 2010.
    @ARTICLE{denise:hal-00483581, author = {Denise, Alain and Ponty, Yann and Termier, Michel},
      title = {{Controlled non uniform random generation of decomposable structures}},
      journal = {Journal of Theoretical Computer Science (TCS)},
      year = {2010},
      volume = {411},
      pages = {3527-3552},
      number = {40-42 },
      abstract = {{Consider a class of decomposable combinatorial structures, using different types of atoms $\Atoms = \{\At\_1,\ldots ,\At\_{|{\Atoms}|}\}$. We address the random generation of such structures with respect to a size $n$ and a targeted distribution in $k$ of its \emph{distinguished} atoms. We consider two variations on this problem. In the first alternative, the targeted distribution is given by $k$ real numbers $\TargFreq\_1, \ldots, \TargFreq\_k$ such that $0 < \TargFreq\_i < 1$ for all $i$ and $\TargFreq\_1+\cdots+\TargFreq\_k \leq 1$. We aim to generate random structures among the whole set of structures of a given size $n$, in such a way that the {\em expected} frequency of any distinguished atom $\At\_i$ equals $\TargFreq\_i$. We address this problem by weighting the atoms with a $k$-tuple $\Weights$ of real-valued weights, inducing a weighted distribution over the set of structures of size $n$. We first adapt the classical recursive random generation scheme into an algorithm taking $\bigO{n^{1+o(1)}+mn\log{n}}$ arithmetic operations to draw $m$ structures from the $\Weights$-weighted distribution. Secondly, we address the analytical computation of weights such that the targeted frequencies are achieved asymptotically, i. e. for large values of $n$. We derive systems of functional equations whose resolution gives an explicit relationship between $\Weights$ and $\TargFreq\_1, \ldots, \TargFreq\_k$. Lastly, we give an algorithm in $\bigO{k n^4}$ for the inverse problem, {\it i.e.} computing the frequencies associated with a given $k$-tuple $\Weights$ of weights, and an optimized version in $\bigO{k n^2}$ in the case of context-free languages. This allows for a heuristic resolution of the weights/frequencies relationship suitable for complex specifications. In the second alternative, the targeted distribution is given by a $k$ natural numbers $n\_1, \ldots, n\_k$ such that $n\_1+\cdots+n\_k+r=n$ where $r \geq 0$ is the number of undistinguished atoms. The structures must be generated uniformly among the set of structures of size $n$ that contain {\em exactly} $n\_i$ atoms $\At\_i$ ($1 \leq i \leq k$). We give a $\bigO{r^2\prod\_{i=1}^k n\_i^2 +m n k \log n}$ algorithm for generating $m$ structures, which simplifies into a $\bigO{r\prod\_{i=1}^k n\_i +m n}$ for regular specifications.}},
      affiliation = {Laboratoire de Recherche en Informatique - LRI , Institut de g{\'e}n{\'e}tique et microbiologie - IGM , AMIB - INRIA Saclay - Ile de France , Laboratoire d'informatique de l'{\'e}cole polytechnique - LIX},
      audience = {internationale },
      doi = {10.1016/j.tcs.2010.05.010 },
      hal_id = {hal-00483581},
      keywords = {G.2.1 G.2.1},
      language = {Anglais},
      pdf = {http://hal.archives-ouvertes.fr/hal-00483581/PDF/NonUniform2009.pdf},
      url = {http://hal.archives-ouvertes.fr/hal-00483581}
    }

Ancienne liste

  • [2012,inproceedings] bibtex
    M. Bouvel and O. Guibert, "Enumeration of permutations sorted with two passes through a stack and $D_8$ symmetries," in To appear in the proceedings of FPSAC 2012 (24th International Conference on Formal Power Series and Algebraic Combinatorics), 2012.
    @inproceedings{, author = {Bouvel, Mathilde and Guibert, Olivier},
      title = {Enumeration of permutations sorted with two passes through a stack and $D_8$ symmetries},
      booktitle = {To appear in the proceedings of FPSAC 2012 (24th International Conference on Formal Power Series and Algebraic Combinatorics)},
      year = {2012}
    }
  • [2012,inproceedings] bibtex
    F. Bassino, M. Bouvel, A. Pierrot, C. Pivoteau, and D. Rossin, "Combinatorial specification of permutation classes," in To appear in the proceedings of FPSAC 2012 (24th International Conference on Formal Power Series and Algebraic Combinatorics), 2012.
    @inproceedings{, author = {Bassino, Fr\'ed\'erique and Bouvel, Mathilde and Pierrot, Adeline and Pivoteau, Carine and Rossin, Dominique},
      title = {Combinatorial specification of permutation classes},
      booktitle = {To appear in the proceedings of FPSAC 2012 (24th International Conference on Formal Power Series and Algebraic Combinatorics)},
      year = {2012}
    }
  • [2012,article] bibtex
    F. Bassino, A. Martino, C. Nicaud, E. Ventura, and P. Weil, "Statistical properties of subgroups of free groups.," Random Structures & Algorithms, 2012.
    @Article{bmnvw12, author = {Fr{\'e}d{\'e}rique Bassino and Armando Martino and Cyril Nicaud and Enric Ventura and Pascal Weil},
      title = {Statistical properties of subgroups of free groups.},
      journal = {Random Structures {\&} Algorithms},
      year = 2012, note = {28 pages - à paraitre},
      }
  • [2012,inproceedings] bibtex
    O. Ait Mous, F. Bassino, and C. Nicaud, "An efficient linear pseudo-minimization algorithm for Aho-Corasick automata," in 23rd Annual Symposium on Combinatorial Pattern Matching (CPM 2012), Helsinki, Finland, 2012, pp. 110-123.
    @InProceedings{abn12c, author = {Ait Mous, Omar and Bassino, Fr{\'e}d{\'e}rique and Nicaud, Cyril},
      title = {An efficient linear pseudo-minimization algorithm for {A}ho-{C}orasick automata},
      booktitle = {23rd Annual Symposium on Combinatorial Pattern Matching (CPM 2012)},
      pages = {110-123},
      year = 2012, volume = {7354},
      series = {Lecture Notes in Computer Science},
      address = {Helsinki, Finland},
      month = {July},
      publisher = {Springer}
    }
  • [2012,inproceedings] bibtex Go to document
    J. Du Boisberranger, D. Gardy, and Y. Ponty, "The weighted words collector," in AOFA – 23rd International Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms – 2012, Montreal, Canada, 2012.
    @inproceedings{DUBOISBERRANGER-2012-666399, hal_id = {hal-00666399},
      url = {http://hal.inria.fr/hal-00666399},
      title = {{The weighted words collector}},
      author = {Du Boisberranger, J{\'e}r{\'e}mie and Gardy, Dani{\`e}le and Ponty, Yann},
      abstract = {{Motivated by applications in bioinformatics, we consider the word collector problem, i.e. the expected number of calls to a random weighted generator of words of length $n$ before the full collection is obtained. The originality of this instance of the non-uniform coupon collector lies in the, potentially large, multiplicity of the words/coupons of a given probability/composition. We obtain a general theorem that gives an asymptotic equivalent for the expected waiting time of a general version of the Coupon Collector. This theorem is especially well-suited for classes of coupons featuring high multiplicities. Its application to a given language essentially necessitates some knowledge on the number of words of a given composition/probability. We illustrate the application of our theorem, in a step-by-step fashion, on three exemplary languages, revealing asymptotic regimes in $\Theta(\mu(n)\cdot n)$ and $\Theta(\mu(n)\cdot \log n)$, where $\mu(n)$ is the sum of weights over words of length $n$.}},
      keywords = {Coupon Collector Problem;Waiting Time;Random Generation;Weighted Context-free Languages},
      language = {Anglais},
      affiliation = {Parall{\'e}lisme, R{\'e}seaux, Syst{\`e}mes d'information, Mod{\'e}lisation - PRISM , Laboratoire d'informatique de l'{\'e}cole polytechnique - LIX , AMIB - INRIA Saclay - Ile de France},
      booktitle = {{AOFA - 23rd International Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms - 2012}},
      pages = {TBA},
      address = {Montreal, Canada},
      organization = {Nicolas, Broutin (INRIA, France) and Luc, Devroye (McGill, Canada)},
      audience = {internationale },
      year = {2012},
      pdf = {http://hal.inria.fr/hal-00666399/PDF/WordCollector-Daniele-Jeremie-Yann-2012.pdf},
      }
  • [2012,inproceedings] bibtex
    B. Morcrette, "Fully analyzing an algebraic Pólya urn model," in LATIN 2012, 2012, pp. 568-581.
    @inproceedings{Morcrette2012, year = {2012},
      author = {Morcrette, Basile},
      title = {Fully analyzing an algebraic {P}\'olya urn model},
      booktitle = {LATIN 2012},
      series = {LNCS},
      volume= {7256},
      pages = {568--581},
      Note = {To appear, April 2012}
    }
  • [2012,inproceedings] bibtex Go to document
    J. Du Boisberranger, D. Gardy, and Y. Ponty, "The weighted words collector," in AOFA – 23rd International Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms – 2012, Montreal, Canada, 2012.
    @inproceedings{duboisberranger:hal-00666399, hal_id = {hal-00666399},
      url = {http://hal.inria.fr/hal-00666399},
      title = {{The weighted words collector}},
      author = {Du Boisberranger, J{\'e}r{\'e}mie and Gardy, Dani{\`e}le and Ponty, Yann},
      keywords = {Coupon Collector Problem;Waiting Time;Random Generation;Weighted Context-free Languages},
      language = {English},
      affiliation = {Parall{\'e}lisme, R{\'e}seaux, Syst{\`e}mes d'information, Mod{\'e}lisation - PRISM , Laboratoire d'informatique de l'{\'e}cole polytechnique - LIX , AMIB - INRIA Saclay - Ile de France},
      booktitle = {{AOFA - 23rd International Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms - 2012}},
      pages = {TBA},
      address = {Montreal, Canada},
      organization = {Nicolas, Broutin (INRIA, France) and Luc, Devroye (McGill, Canada)},
      audience = {international },
      year = {2012},
      pdf = {http://hal.inria.fr/hal-00666399/PDF/WordCollector-Daniele-Jeremie-Yann-2012.pdf},
      }
  • [2012,article] bibtex
    F. Bassino, J. David, and C. Nicaud, "Average Case Analysis of Moore’s State Minimization Algorithm," Algorithmica, vol. 63, iss. 1–2, pp. 509-531, 2012.
    @Article{bdn12j, author = {Fr{\'e}d{\'e}rique Bassino and Julien David and Cyril Nicaud},
      title = {Average Case Analysis of {M}oore's State Minimization Algorithm},
      journal = {Algorithmica},
      year = 2012, volume = 63, number = {1--2},
      pages = {509--531}
    }
  • [2012,article] bibtex
    F. Bassino, J. Clément, and P. Nicodème, "Counting occurrences for a finite set of words: combinatorial methods," ACM Transactions on Algorithms, 2012.
    @Article{bcn11, author = {Bassino, Fr{\'e}d{\'e}rique and Cl{\'e}ment, Julien and Nicod{\`e}me, Pierre},
      title = {Counting occurrences for a finite set of words: combinatorial methods},
      journal = {ACM Transactions on Algorithms},
      year = 2012, note = {28 pages- à paraitre en Juillet}
    }
  • [2012,inproceedings] bibtex Go to document
    P. Rinaudo, Y. Ponty, D. Barth, and A. Denise, "Tree decomposition and parameterized algorithms for RNA structure-sequence alignment including tertiary interactions and pseudoknots," in WABI – 12th Workshop on Algorithms in Bioinformatics – 2012, Ljubljana, Slovenia, 2012.
    @inproceedings{rinaudo:hal-00708580, hal_id = {hal-00708580},
      url = {http://hal.inria.fr/hal-00708580},
      title = {{Tree decomposition and parameterized algorithms for RNA structure-sequence alignment including tertiary interactions and pseudoknots}},
      author = {Rinaudo, Philippe and Ponty, Yann and Barth, Dominique and Denise, Alain},
      keywords = {RNA structure; sequence-structure alignment; tree-decomposition},
      language = {English},
      affiliation = {Laboratoire de Recherche en Informatique - LRI , AMIB - INRIA Saclay - Ile de France , Parall{\'e}lisme, R{\'e}seaux, Syst{\`e}mes d'information, Mod{\'e}lisation - PRISM , Laboratoire d'informatique de l'{\'e}cole polytechnique - LIX , Institut de g{\'e}n{\'e}tique et microbiologie - IGM},
      booktitle = {{WABI - 12th Workshop on Algorithms in Bioinformatics - 2012}},
      address = {Ljubljana, Slovenia},
      organization = {University of Ljubljana},
      editor = {Ben Raphael and Jijun Tang },
      note = {Support from the DIGITEO RNAomics project },
      audience = {international },
      year = {2012},
      pdf = {http://hal.inria.fr/hal-00708580/PDF/article.pdf},
      }
  • [2012,inproceedings] bibtex
    B. Morcrette and H. M. Mahmoud, "Exactly solvable balanced tenable urns with random entries via the analytic methodology," in Analysis of Algorithms (AofA) 2012, 2012.
    @inproceedings{MoMa12, year = {2012},
      author = {Morcrette, Basile and Mahmoud, Hosam M.},
      title = {Exactly solvable balanced tenable urns with random entries via the analytic methodology},
      booktitle = {Analysis of Algorithms (AofA) 2012},
      series = {DMTCS Proceedings},
      volume= {},
      pages = {},
      Note = {To appear, June 2012}
    }
  • [2012,inproceedings] bibtex Go to document
    C. Banderier, O. Bodini, Y. Ponty, and H. Tafat, "On the diversity of pattern distributions in combinatorial systems," in Proceedings of the 12th Meeting on Analytic Algorithmics \& Combinatorics, Kyoto, Japon, 2012, pp. 107-116.
    @inproceedings{BANDERIER-2012-643598, hal_id = {hal-00643598},
      url = {http://hal.archives-ouvertes.fr/hal-00643598},
      title = {{On the diversity of pattern distributions in combinatorial systems}},
      author = {Banderier, Cyril and Bodini, Olivier and Ponty, Yann and Tafat, Hanane},
      abstract = {{It is well known that, under some aperiodicity and irreducibility conditions, the number of occurrences of local patterns within a Markov chain (and, more generally, within the languages generated by weighted regular expressions/automata) follows a Gaussian distribu- tion with both variance and mean in (n). By contrast, when these conditions no longer hold, it has been denoted that the limiting distribution may follow a whole diversity of distributions, including the uniform, power-law or even multimodal distribution, arising as tradeo s between structural properties of the regular expression and the weight/probabilities associated with its transitions/letters. However these cases only partially cover the full diversity of behaviors induced within regular expressions, and a characterization of attainable distributions remained to be provided. In this article, we constructively show that the limiting distribution of the simplest foresee- able motif (a single letter!) may already follow an arbitrarily complex continuous distribution (or cadlag process). We also give applications in random generation (Boltzmann sampling) and bioinformatics (parsimonious segmentation of DNA).}},
      language = {Anglais},
      affiliation = {Laboratoire d'informatique de Paris-nord - LIPN , Laboratoire d'informatique de l'{\'e}cole polytechnique - LIX , AMIB - INRIA Saclay - Ile de France},
      booktitle = {{Proceedings of the 12th Meeting on Analytic Algorithmics \& Combinatorics}},
      publisher = {Omnipress},
      pages = {107--116},
      address = {Kyoto, Japon},
      audience = {internationale },
      year = {2012},
      pdf = {http://hal.archives-ouvertes.fr/hal-00643598/PDF/analco\_soda.pdf},
      }
  • [2012,article] bibtex
    X. Wang, M. Latapy, and M. Soria, "Deciding on the type of the degree distribution of a graph from traceroute-like measurements," IJCNC/IJDPS, p. 1, 2012.
    @ARTICLE{LIP68105, author = {Wang, Xiaomin and Latapy, Matthieu and Soria, Mich{\`{e}}le},
      x-lip6teams = {APR, COMPLEXNETWORKS},
      x-lip6id = {8105},
      x-international-audience = {yes},
      title = {Deciding on the type of the degree distribution of a graph from traceroute-like measurements},
      journal = {IJCNC/IJDPS},
      year = {2012},
      pages = {1, 20},
      note = {To appear}
    }
  • [2012,inproceedings] bibtex Go to document
    S. Sheikh, R. Backofen, and Y. Ponty, "Impact Of The Energy Model On The Complexity Of RNA Folding With Pseudoknots," in CPM – 23rd Annual Symposium on Combinatorial Pattern Matching – 2012, Helsinki, Finland, 2012.
    @inproceedings{sheikh:hal-00670232, hal_id = {hal-00670232},
      url = {http://hal.inria.fr/hal-00670232},
      title = {{Impact Of The Energy Model On The Complexity Of RNA Folding With Pseudoknots}},
      author = {Sheikh, Saad and Backofen, Rolf and Ponty, Yann},
      keywords = {RNA folding;General pseudoknots;Hardness;Inapproximability},
      language = {English},
      affiliation = {Laboratoire d'informatique de l'{\'e}cole polytechnique - LIX , AMIB - INRIA Saclay - Ile de France , Albert-Ludwigs University - ALBERT-LUDWIGS UNIVERSITY},
      booktitle = {{CPM - 23rd Annual Symposium on Combinatorial Pattern Matching - 2012}},
      pages = {TBA},
      address = {Helsinki, Finland},
      organization = {Juha K{\"a}rkk{\"a}inen},
      editor = {Juha K{\"a}rkk{\"a}inen and Jens Stoye },
      audience = {international },
      year = {2012},
      pdf = {http://hal.inria.fr/hal-00670232/PDF/NPCompleteness-Stacking.pdf},
      }
  • [2012,inproceedings] bibtex
    F. Bassino, C. Nicaud, and P. Weil, "Generic properties of random subgroups of a free group for general distributions," in 23rd International Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2012), Montréal, Canada, 2012, pp. 155-166.
    @InProceedings{bnw12c, author = {Fr{\'e}d{\'e}rique Bassino and Cyril Nicaud and Pascal Weil},
      title = {Generic properties of random subgroups of a free group for general distributions},
      booktitle = {23rd International Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2012)},
      pages = {155-166},
      year = 2012, volume = {},
      series = {Discrete Mathematics \& Theoretical Computer Science Proceedings},
      address = {Montr{\'e}al, Canada},
      month = {June},
      note={12 pages}
    }
  • [2012,inproceedings] bibtex
    P. Nicodème, "Revisiting Waiting Times in DNA Evolution," in NCMA2012, 2012.
    @inproceedings{Nicodeme2012, author = {Nicod\`eme, P.},
      title = {Revisiting {W}aiting {T}imes in {D}{N}{A} {E}volution},
      booktitle = {NCMA2012},
      year = {2012},
      note = {Accepted for the Fourth International Workshop on Non-Classical Models of Automata and Applications, Aug. 2012, Fribourg, Switzerland, 18 pages}
    }
  • [2012,inproceedings] bibtex Go to document
    A. Busic, N. Fates, J. Mairesse, and I. Marcovici, "Density classification on infinite lattices and trees," in Proceedings of the 10th Latin American conference on Theoretical Informatics, Berlin, Heidelberg, 2012, pp. 109-120.
    @InProceedings{, author = {Ana Busic and Nazim Fates and Jean Mairesse and Irene Marcovici},
      title = {{Density classification on infinite lattices and trees}},
      booktitle = {Proceedings of the 10th Latin American conference on Theoretical Informatics},
      pages = {109--120},
      series = {Lecture Notes in Computer Science},
      ISBN = {},
      ISSN = {},
      year = {2012},
      volume = {},
      editor = {David Fern\`andez-Baca},
      publisher = {Springer-Verlag},
      address = {Berlin, Heidelberg},
      URL = {},
      URN = {},
      doi = {},
      annote = {Keywords: cellular automata, interacting particle systems, density classification, percolation}
    }
  • [2012,article] bibtex
    C. Pivoteau, B. Salvy, and M. Soria, "Algorithms for combinatorial structures: Well-founded systems and Newton iterations," Journal of Combinatorial Theory, Series A (JCTA), vol. 119, p. 1711, 2012.
    @ARTICLE{LIP64891, author = {Pivoteau, Carine and Salvy, Bruno and Soria, Mich{\`{e}}le},
      x-lip6teams = {APR},
      x-lip6id = {4891},
      x-international-audience = {yes},
      title = {Algorithms for combinatorial structures: Well-founded systems and Newton iterations},
      journal = {Journal of Combinatorial Theory, Series A (JCTA)},
      volume = {119},
      year = {2012},
      pages = {1711–1773}
    }
  • [2012,article] bibtex
    O. Bodini, O. Roussel, and M. Soria, "Boltzmann samplers for first order combinatorial differential equations," Discrete Applied Mathematics, pp. 1-17 to appear, 2012.
    @ARTICLE{LIP64256, author = {Bodini, Olivier and Roussel, Olivier and Soria, Mich{\`{e}}le},
      x-lip6teams = {APR},
      x-lip6id = {4256},
      x-international-audience = {yes},
      title = {Boltzmann samplers for first order combinatorial differential equations},
      journal = {Discrete Applied Mathematics},
      year = {2012},
      pages = {1-17 to appear},
      labs={LIP6},
      teams={APR},
      pub_status={INT},
      }
  • [2012,inproceedings] bibtex
    O. Bodini and J. Lumbroso, "Dirichlet Random Samplers for Multiplicative Structures," in Proceedings of the Ninth Meeting on Analytic Algorithmics and Combinatorics (ANALCO’12), 2012, pp. 92-106.
    @inproceedings{BoLu12, author = {Bodini, Olivier and Lumbroso, J\'er\'emie},
      title = {Dirichlet Random Samplers for Multiplicative Structures},
      booktitle = {Proceedings of the Ninth Meeting on Analytic Algorithmics and Combinatorics (ANALCO'12)},
      location = {Kyoto, Japan},
      pages = {92--106},
      year = {2012},
      month = {January},
      publisher = {SIAM}
    }
  • [2012,inproceedings] bibtex
    F. Bassino, J. David, and A. Sportiello, "Asymptotic enumeration of minimal automata," in 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012), Paris, France, 2012, p. 88.
    @InProceedings{bds12c, author = {Fr{\'e}d{\'e}rique Bassino and Julien David and Andrea Sportiello},
      title = {Asymptotic enumeration of minimal automata},
      booktitle = {29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
      pages = {88 99},
      year = 2012, volume = 14, series = {Leibniz International Proceedings in Informatics (LIPIcs)},
      address = {Paris, France},
      month = {March},
      note = {www.stacs-conf.org},
      }
  • [2012,article] bibtex
    A. Darrasse, K. Panagiotou, O. Roussel, and M. Soria, "Biased Boltzmann samplers and generation of extended linear languages with shuffle," DIMACS Series in Discrete Mathematics and Theoretical Computer Science International Conference on Analysis of Algorithms, Montréal, pp. 1-12, 2012.
    @ARTICLE{LIP65601, author = {Darrasse, Alexis and Panagiotou, Konstantinos and Roussel, Olivier and Soria, Mich{\`{e}}le},
      x-lip6teams = {APR},
      x-lip6id = {5601},
      x-international-audience = {yes},
      title = {Biased Boltzmann samplers and generation of extended linear languages with shuffle},
      journal = {DIMACS Series in Discrete Mathematics and Theoretical Computer Science International Conference on Analysis of Algorithms, Montr{\'{e}}al},
      year = {2012},
      pages = {1-12}
    }
  • [2011,inproceedings] bibtex Go to document
    J. Waldispühl and Y. Ponty, "An unbiased adaptive sampling algorithm for the exploration of RNA mutational landscapes under evolutionary pressure," in Research in Computational Molecular Biology, Vancouver, Canada, 2011, pp. 501-515.
    @inproceedings{waldispuhl:hal-00546847, hal_id = {hal-00546847},
      url = {http://hal.archives-ouvertes.fr/hal-00546847},
      title = {{An unbiased adaptive sampling algorithm for the exploration of RNA mutational landscapes under evolutionary pressure}},
      author = {Waldisp{\"u}hl, J{\'e}r{\^o}me and Ponty, Yann},
      language = {English},
      affiliation = {McGill University , AMIB - INRIA Saclay - Ile de France , Laboratoire d'informatique de l'{\'e}cole polytechnique - LIX},
      booktitle = {{Research in Computational Molecular Biology}},
      publisher = {Springer Berlin / Heidelberg},
      pages = {501-515},
      address = {Vancouver, Canada},
      volume = {6577},
      editor = {Bafna, Vineet and Sahinalp, S. },
      series = {Lecture Notes in Computer Science },
      audience = {international },
      doi = {10.1007/978-3-642-20036-6\_45 },
      year = {2011},
      pdf = {http://hal.archives-ouvertes.fr/hal-00546847/PDF/paper.pdf},
      }
  • [2011,inproceedings] bibtex Go to document
    P. Flajolet, M. Pelletier, and M. Soria, "On Buffon Machines and Numbers," in SODA’11, 2011, p. pp. 172-183.
    @INPROCEEDINGS{LIP64277, author = {Flajolet, Philippe and Pelletier, Maryse and Soria, Mich{\`{e}}le},
      x-lip6teams = {APR},
      x-lip6id = {4277},
      x-international-audience = {yes},
      title = {On Buffon Machines and Numbers},
      booktitle = {SODA'11},
      year = {2011},
      pages = {pp. 172-183},
      location = {San Francisco {\'{E}}tats-Unis},
      url = {http://hal.archives-ouvertes.fr/hal-00548904/en/},
      labs={LIP6},
      teams={APR},
      pub_status={INT},
      }
  • [2011,inproceedings] bibtex Go to document
    Y. Ponty and C. Saule, "A Combinatorial Framework for Designing (Pseudoknotted) RNA Algorithms," in 11th Workshop on Algorithms in Bioinformatics (WABI’11), Saarbrucken, Germany, 2011.
    @inproceedings{ponty:inria-00601060, hal_id = {inria-00601060},
      url = {http://hal.inria.fr/inria-00601060},
      title = {{A Combinatorial Framework for Designing (Pseudoknotted) RNA Algorithms}},
      author = {Ponty, Yann and Saule, C{\'e}dric},
      language = {English},
      affiliation = {AMIB - INRIA Saclay - Ile de France , Laboratoire d'informatique de l'{\'e}cole polytechnique - LIX , Laboratoire de Recherche en Informatique - LRI , Institut de Recherche en Immunologie et en Canc{\'e}rologie - IRIC},
      booktitle = {{11th Workshop on Algorithms in Bioinformatics (WABI'11)}},
      address = {Saarbrucken, Germany},
      audience = {international },
      year = {2011},
      pdf = {http://hal.inria.fr/inria-00601060/PDF/BoltzmannEnsembleWithPK.pdf},
      }
  • [2011,inproceedings] bibtex
    G. Giakkoupis and N. Schabanel, "Optimal Path Search in Small Worlds: Dimension Matters," in Proc of ACM Symp. on Theory of Computing (STOC), 2011, pp. 393-402.
    @inproceedings{GiakkoupisSchabanel2010STOC, Author = {George Giakkoupis and Nicolas Schabanel},
      Booktitle = {Proc of ACM Symp. on Theory of Computing (STOC)},
      Pages = {393-402},
      Title = {Optimal Path Search in Small Worlds: Dimension Matters},
      Volume = {43},
      Year = {2011}
    }
  • [2011,inproceedings] bibtex
    J. Mairesse, A. Micheli, and D. Poulalhon, "Minimizing braids on four strands," in Braids, 2011.
    @InProceedings{mmp11a, keywords = {c-com},
      author = {J. Mairesse and A. Micheli and D. Poulalhon},
      title = {Minimizing braids on four strands},
      booktitle = {Braids},
      year = 2011 }
  • [2011,misc] bibtex
    N. Schabanel, On stochastic cellular Automata, 2011.
    @misc{Schabanel2011Automata, Author = {Nicolas Schabanel},
      Howpublished = {Plenary invited talk at Int. Conf. Automata 2011, Santiago de Chile},
      Month = {Nov.},
      Title = {On stochastic cellular Automata},
      Year = {2011}
    }
  • [2011,misc] bibtex
    N. Schabanel, Complex systems from a computer science point of view., 2011.
    @misc{Schabanel2011Disco, Author = {Nicolas Schabanel},
      Howpublished = {Invited talk at Int. Conf. Dynamics of Complex systems (Disco), Valpara{\'\i}so de Chile},
      Month = {Nov.},
      Title = {Complex systems from a computer science point of view.},
      Year = {2011}
    }
  • [2011,article] bibtex
    F. Bassino, M. Bouvel, and D. Rossin, "Enumeration of pin-permutations," Electronic Journal of Combinatorics, vol. 18, 2011.
    @Article{BBR09, author = {Bassino, Fr{\'e}d{\'e}rique and Bouvel, Mathilde and Rossin, Dominique},
      title = {Enumeration of pin-permutations},
      journal = {Electronic Journal of Combinatorics},
      year = {2011},
      volume = {18},
      issue = {1},
      annote = {paper P.57}
    }
  • [2011,article] bibtex
    M. Bouvel, C. Chauve, M. Mishna, and D. Rossin, "Average-case analysis of perfect sorting by reversals," Discrete Mathematics, Algorithms and Applications, vol. 3, iss. 3, 2011.
    @Article{bcmr11, author = {Bouvel, Mathilde and Chauve, C\'edric and Mishna, Marni and Rossin, Dominique},
      title = {Average-case analysis of perfect sorting by reversals},
      journal = {Discrete Mathematics, Algorithms and Applications},
      year = {2011},
      volume = {3},
      number = {3},
      }
  • [2011,article] bibtex
    F. Bassino, M. Bouvel, and D. Rossin, "Enumeration of Pin-Permutations," Electronic Journal of Combinatorics, vol. 18, iss. 1, 2011.
    @Article{bbr11, author = {Bassino, Fr\'ed\'erique and Bouvel, Mathilde and Rossin, Dominique},
      title = {Enumeration of Pin-Permutations},
      journal = {Electronic Journal of Combinatorics},
      year = {2011},
      volume = {18},
      number = {1},
      note = {Paper P57},
      }
  • [2011,inproceedings] bibtex
    J. Mairesse, A. Micheli, and D. Poulalhon, "Comment minimiser une tresse," in Journées de Combinatoire de Bordeaux, 2011.
    @InProceedings{mmp11b, keywords = {c-com},
      author = {J. Mairesse and A. Micheli and D. Poulalhon},
      title = {Comment minimiser une tresse},
      booktitle = {Journ\'ees de Combinatoire de Bordeaux},
      year = 2011 }
  • [2011,inproceedings] bibtex Go to document
    A. Busic, J. Mairesse, and I. Marcovici, "Probabilistic cellular automata, invariant measures, and perfect sampling," in 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011), Dagstuhl, Germany, 2011, pp. 296-307.
    @InProceedings{busic_et_al:LIPIcs:2011:3019, author = {Ana Busic and Jean Mairesse and Irene Marcovici},
      title = {{Probabilistic cellular automata, invariant measures, and perfect sampling}},
      booktitle = {28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
      pages = {296--307},
      series = {Leibniz International Proceedings in Informatics (LIPIcs)},
      ISBN = {978-3-939897-25-5},
      ISSN = {1868-8969},
      year = {2011},
      volume = {9},
      editor = {Thomas Schwentick and Christoph D{\"u}rr},
      publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
      address = {Dagstuhl, Germany},
      URL = {http://drops.dagstuhl.de/opus/volltexte/2011/3019},
      URN = {urn:nbn:de:0030-drops-30190},
      doi = {http://dx.doi.org/10.4230/LIPIcs.STACS.2011.296},
      annote = {Keywords: probabilistic cellular automata, perfect sampling, ergodicity}
    }
  • [2011,article] bibtex Go to document
    P. Clote, Y. Ponty, and J. Steyaert, "Expected distance between terminal nucleotides of RNA secondary structures," Journal of Mathematical Biology, pp. 1-19, 2011.
    @article{clote:inria-00619921, hal_id = {inria-00619921},
      url = {http://hal.inria.fr/inria-00619921},
      title = {{Expected distance between terminal nucleotides of RNA secondary structures}},
      author = {Clote, Peter and Ponty, Yann and Steyaert, Jean-Marc},
      language = {English},
      affiliation = {Laboratoire d'informatique de l'{\'e}cole polytechnique - LIX , Department of Biology , AMIB - INRIA Saclay - Ile de France},
      publisher = {Springer},
      pages = {1-19},
      journal = {Journal of Mathematical Biology},
      audience = {international },
      year = {2011},
      pdf = {http://hal.inria.fr/inria-00619921/PDF/paper.pdf},
      }
  • [2011,article] bibtex Go to document
    J. Waldispühl and Y. Ponty, "An unbiased adaptive sampling algorithm for the exploration of RNA mutational landscapes under evolutionary pressure.," Journal of Computational Biology, vol. 18, iss. 11, pp. 1465-79, 2011.
    @article{waldispuhl:hal-00681928, hal_id = {hal-00681928},
      url = {http://hal.inria.fr/hal-00681928},
      title = {{An unbiased adaptive sampling algorithm for the exploration of RNA mutational landscapes under evolutionary pressure.}},
      author = {Waldisp{\"u}hl, J{\'e}r{\^o}me and Ponty, Yann},
      language = {English},
      affiliation = {McGill University , Laboratoire d'informatique de l'{\'e}cole polytechnique - LIX , AMIB - INRIA Saclay - Ile de France},
      publisher = {Mary Ann Liebert},
      pages = {1465-79},
      journal = {Journal of Computational Biology},
      volume = {18},
      number = {11 },
      audience = {international },
      doi = {10.1089/cmb.2011.0181 },
      year = {2011},
      month = Nov, }
  • [2010,article] bibtex
    F. Bassino, M. Bouvel, A. Pierrot, and D. Rossin, "Deciding the finiteness of the number of simple permutations contained in a wreath-closed class is polynomial," Pure Mathematics and Applications, vol. 21, iss. 2, 2010.
    @Article{bbpr10, author = {Bassino, Fr\'ed\'erique and Bouvel, Mathilde and Pierrot, Adeline and Rossin, Dominique},
      title = {Deciding the finiteness of the number of simple permutations contained in a wreath-closed class is polynomial},
      journal = {Pure Mathematics and Applications},
      year = {2010},
      volume = {21},
      number = {2},
      }
  • [2010,article] bibtex
    F. Bassino, M. Bouvel, A. Pierrot, and D. Rossin, "Deciding the finiteness of simple permutations contained in a wreath-closed class is polynomial," Pure Mathematics and Applications, vol. 21, iss. 2, pp. 119-135, 2010.
    @Article{BBPR09, author = {Bassino, Fr{\'e}d{\'e}rique and Bouvel, Mathilde and Pierrot, Adeline and Rossin, Dominique},
      title = {Deciding the finiteness of simple permutations contained in a wreath-closed class is polynomial},
      journal = {Pure Mathematics and Applications},
      year = {2010},
      volume = {21},
      number = {2},
      pages = {119--135},
      }

Leave a Reply