Liste des publications de Magnum extraite de Hal :

[2013,article] bibtexO. Cheong, X. Goaoc, and C. Nicaud, "Set Systems and Families of Permutations with Small Traces," European Journal of Combinatorics, vol. 34, pp. 229239, 2013.
@ARTICLE{cheong:hal00752064, 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 = {229239},
owner = {Yawn},
publisher = {Elsevier},
timestamp = {2013.03.11},
url = {http://hal.inria.fr/hal00752064}
} 
[2013,inproceedings] bibtexV. Reinharz, Y. Ponty, and J. Waldispühl, "A linear insideoutside 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:hal00766781, author = {Reinharz, Vladimir and Ponty, Yann and Waldisp{\"u}hl, J{\'e}r{\^o}me},
title = {{A linear insideoutside 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/hal00766781}
} 
[2013,inproceedings] bibtexE. 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:hal00766780, 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/hal00766780}
} 
[2013,article] bibtexA. Lorenz and Y. Ponty, "Nonredundant random generation algorithms for weighted contextfree languages," Theoretical Computer Science, 2013.
@ARTICLE{lorenz:inria00607745, author = {Lorenz, Andy and Ponty, Yann},
title = {{Nonredundant random generation algorithms for weighted contextfree languages}},
journal = {{Theoretical Computer Science}},
year = {2013},
pages = {To appear},
owner = {Yawn},
publisher = {Elsevier},
timestamp = {2013.03.11},
url = {http://hal.inria.fr/inria00607745}
} 
[2012,inproceedings] bibtexJ. 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:hal00723333, 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/hal00723333}
} 
[2012,inproceedings] bibtexJ. 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. 243264.
@INPROCEEDINGS{duboisberranger:hal00666399, 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 = {243264},
address = {Montreal, Canada},
organization = {Nicolas, Broutin (INRIA, France) and Luc, Devroye (McGill, Canada)},
publisher = {DMTCS},
keywords = {Coupon Collector Problem;Waiting Time;Random Generation;Weighted Contextfree Languages},
owner = {Yawn},
timestamp = {2013.03.11},
url = {http://hal.inria.fr/hal00666399}
} 
[2012,article] bibtexE. 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:hal00769740, 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/hal00769740}
} 
[2012,inproceedings] bibtexS. 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:hal00670232, 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 freeenergy matching of its $n$ positions. Assuming independently contributing basepairs, 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 NPHard in the more realistic nearestneighbor energy model. In this work, we consider an intermediate model, called the stackingpairs energy model. We extend a result by Lyngs\o, showing that RNA folding with PK is NPHard 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 nearestneighbor 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 , AlbertLudwigs University  ALBERTLUDWIGS UNIVERSITY},
audience = {internationale },
hal_id = {hal00670232},
keywords = {RNA folding;General pseudoknots;Hardness;Inapproximability},
language = {Anglais},
pdf = {http://hal.inria.fr/hal00670232/PDF/NPCompletenessStacking.pdf},
url = {http://hal.inria.fr/hal00670232}
} 
[2012,inproceedings] bibtexP. Rinaudo, Y. Ponty, D. Barth, and A. Denise, "Tree decomposition and parameterized algorithms for RNA structuresequence alignment including tertiary interactions and pseudoknots," in WABI – 12th Workshop on Algorithms in Bioinformatics – 2012, Ljubljana, Slovénie, 2012.
@INPROCEEDINGS{rinaudo:hal00708580, author = {Rinaudo, Philippe and Ponty, Yann and Barth, Dominique and Denise, Alain},
title = {{Tree decomposition and parameterized algorithms for RNA structuresequence 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 structuresequence 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 = {hal00708580},
keywords = {RNA structure; sequencestructure alignment; treedecomposition},
language = {Anglais},
pdf = {http://hal.inria.fr/hal00708580/PDF/article.pdf},
url = {http://hal.inria.fr/hal00708580}
} 
[2012,article] bibtexM. 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:hal00640059, 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/hal00640059}
} 
[2012,inproceedings] bibtexC. 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. 107116.
@INPROCEEDINGS{banderier:hal00643598, 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 = {107116},
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, powerlaw 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 Parisnord  LIPN , Laboratoire d'informatique de l'{\'e}cole polytechnique  LIX , AMIB  INRIA Saclay  Ile de France},
audience = {internationale },
hal_id = {hal00643598},
language = {Anglais},
pdf = {http://hal.archivesouvertes.fr/hal00643598/PDF/analco\_soda.pdf},
url = {http://hal.archivesouvertes.fr/hal00643598}
} 
[2012,article] bibtexC. Pivoteau, B. Salvy, and M. Soria, "Algorithms for combinatorial structures: Wellfounded systems and Newton iterations.," Journal of Combinatorial Theory, Series A, vol. 119, iss. 8, pp. 17111773, 2012.
@ARTICLE{pivoteau:inria00622853, author = {Pivoteau, Carine and Salvy, Bruno and Soria, Michele},
title = {{Algorithms for combinatorial structures: Wellfounded systems and Newton iterations.}},
journal = {{Journal of Combinatorial Theory, Series A}},
year = {2012},
volume = {119},
pages = {17111773},
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/inria00622853}
} 
[2012,article] bibtexC. Banderier and P. Hitczenko, "Enumeration and asymptotics of restricted compositions having the same number of parts," Discrete Applied Mathematics, pp. 113, 2012.
@ARTICLE{banderier:hal00664192, 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 = {113},
doi = {10.1016/j.dam.2011.12.011},
keywords = {Integer composition; Pairs of combinatorial structures; Local limit theorem; Asymptotics of Dfinite sequences; Diagonal of algebraic generating function},
owner = {Yawn},
timestamp = {2013.03.11},
url = {http://hal.inria.fr/hal00664192}
} 
[2012,inproceedings] bibtexB. 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. 219232.
@INPROCEEDINGS{morcrette:hal00719639, 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. 219232},
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/hal00719639}
} 
[2012,inproceedings] bibtexA. 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. 194205.
@INPROCEEDINGS{carayol:hal00678213, 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 = {194205},
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/hal00678213}
} 
[2012,inproceedings] bibtexI. 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. 109120.
@INPROCEEDINGS{marcovici:hal00712614, 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 FernandezBaca },
volume = {7256},
series = {Lecture Notes in Computer Science },
pages = {109120},
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 finiterange 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/9783642293443\_10 },
hal_id = {hal00712614},
keywords = {Cellular automata ; interacting particle systems ; density classification ; percolation},
language = {Anglais},
url = {http://hal.archivesouvertes.fr/hal00712614}
} 
[2012,article] bibtexA. Busic, B. Gaujal, and F. Pin, "Perfect Sampling of Markov Chains with Piecewise Homogeneous Events," Performance Evaluation, vol. 69, iss. 6, pp. 247266, 2012.
@ARTICLE{busic:hal00787997, 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 = {247266},
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/hal00787997}
} 
[2012,article] bibtexA. 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. 1004152, 2012.
@ARTICLE{levin:hal00733924, 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 = {1004152},
number = {20},
month = Nov, doi = {10.1093/nar/gks768},
owner = {Yawn},
publisher = {Oxford University Press},
timestamp = {2013.03.11},
url = {http://hal.inria.fr/hal00733924}
} 
[2012,inproceedings] bibtexA. 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. 136149.
@INPROCEEDINGS{busic:hal00788003, 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 AlBegain and Dieter Fiems and JeanMarc Vincent},
volume = {7314},
series = {Lecture Notes in Computer Science},
pages = {136149},
address = {Grenoble, France},
publisher = {Springer},
doi = {10.1007/9783642307829\_10},
owner = {Yawn},
timestamp = {2013.03.11},
url = {http://hal.inria.fr/hal00788003}
} 
[2012,inproceedings] bibtexS. Janssen, L. Paulevé, Y. Ponty, B. Raman, and M. Zytnicki, "Can Probabilistic Model Checking Explore RiboNucleic Acid Folding Space?," in IWBDA – 4th International Workshop on BioDesign Automation – 2012, San Francisco, ÉtatsUnis, 2012.
@INPROCEEDINGS{janssen:hal00712557, author = {Janssen, Stefan and Paulev{\'e},
Lo{\"\i}c and Ponty, Yann and Raman, Balaji and Zytnicki, Matthias},
title = {{Can Probabilistic Model Checking Explore RiboNucleic Acid Folding Space?}},
booktitle = {{IWBDA  4th International Workshop on BioDesign Automation  2012}},
year = {2012},
address = {San Francisco, {\'E}tatsUnis},
owner = {Yawn},
timestamp = {2013.03.11},
url = {http://hal.inria.fr/hal00712557}
} 
[2012,inproceedings] bibtexM. Bouvel and O. Guibert, "Refined enumeration of permutations sorted with two stacks and a D\_8symmetry," in FPSAC 2012 (24th International Conference on Formal Power Series and Algebraic Combinatorics), Nagoya, Japon, 2012, pp. 757768.
@INPROCEEDINGS{bouvel:hal00749260, author = {Bouvel, Mathilde and Guibert, Olivier},
title = {{Refined enumeration of permutations sorted with two stacks and a D\_8symmetry}},
booktitle = {{FPSAC 2012 (24th International Conference on Formal Power Series and Algebraic Combinatorics)}},
year = {2012},
volume = {AR},
pages = {757768},
address = {Nagoya, Japon},
owner = {Yawn},
timestamp = {2013.03.11},
url = {http://hal.inria.fr/hal00749260}
} 
[2012,inproceedings] bibtexB. Morcrette, "Fully Analyzing an Algebraic Polya Urn Model," in LATIN 2012, LNCS 7256, Arequipa, Pérou, 2012, p. pp. 568581.
@INPROCEEDINGS{morcrette:hal00675936, author = {Morcrette, Basile},
title = {{Fully Analyzing an Algebraic Polya Urn Model}},
booktitle = {{LATIN 2012, LNCS 7256}},
year = {2012},
editor = {D. FernandezBaca Ed. },
volume = {LNCS 7256},
pages = {pp. 568581},
address = {Arequipa, P{\'e}rou},
publisher = {SpringerVerlag 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" pointofview, following in the footsteps of FlajoletDumasPuyhaubert, 2006. Through an algebraic generating function to which we apply a multiple coalescing saddlepoint 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 = {hal00675936},
keywords = {analytic combinatorics; Polya urn models; multiple coalescing saddlepoint method; Gaussian local limit law; large deviations},
language = {Anglais},
pdf = {http://hal.archivesouvertes.fr/hal00675936/PDF/morcrette\_latin2012.pdf},
url = {http://hal.archivesouvertes.fr/hal00675936}
} 
[2012,inproceedings] bibtexA. Genitrini, O. Bodini, and F. Peschanski, "Enumeration and Random Generation of Concurrent Computations," in DMTCS, Canada, 2012.
@INPROCEEDINGS{genitrini:hal00699964, 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 Parisnord  LIPN},
audience = {internationale },
collaboration = {APR, CALIN },
hal_id = {hal00699964},
language = {Anglais},
url = {http://hal.archivesouvertes.fr/hal00699964}
} 
[2012,article] bibtexF. Bassino, J. David, and C. Nicaud, "Average Case Analysis of Moore’s State Minimization Algorithm," Algorithmica, vol. 63, iss. 1, pp. 509531, 2012.
@ARTICLE{bassino:hal00619784, 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 = {509531},
number = {1},
owner = {Yawn},
timestamp = {2013.03.11},
url = {http://hal.inria.fr/hal00619784}
} 
[2012,inproceedings] bibtexJ. 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:hal00666399, 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 nonuniform 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 wellsuited 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 stepbystep 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 = {hal00666399},
keywords = {Coupon Collector Problem;Waiting Time;Random Generation;Weighted Contextfree Languages},
language = {Anglais},
pdf = {http://hal.inria.fr/hal00666399/PDF/WordCollectorDanieleJeremieYann2012.pdf},
url = {http://hal.inria.fr/hal00666399}
} 
[2012,inproceedings] bibtexF. 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. 781792.
@INPROCEEDINGS{bassino:hal00685023, 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/hal00685023}
} 
[2012,inproceedings] bibtexO. Aitmous, F. Bassino, and C. Nicaud, "An Efficient Linear PseudoMinimization Algorithm for AhoCorasick Automata," in 23st Annual Symposium on Combinatorial Pattern Matching (CPM’12), Finlande, 2012, pp. 110123.
@INPROCEEDINGS{aitmous:hal00793395, author = {Aitmous, Omar and Bassino, Fr{\'e}d{\'e}rique and Nicaud, Cyril},
title = {{An Efficient Linear PseudoMinimization Algorithm for AhoCorasick Automata}},
booktitle = {{23st Annual Symposium on Combinatorial Pattern Matching (CPM'12)}},
year = {2012},
volume = {7354},
pages = {110123},
address = {Finlande},
owner = {Yawn},
timestamp = {2013.03.11},
url = {http://hal.inria.fr/hal00793395}
} 
[2012,article] bibtexF. Bassino, A. Martino, C. Nicaud, E. Ventura, and P. Weil, "Statistical properties of subgroups of free groups," Random Structures and Algorithms, 2012.
@ARTICLE{bassino:hal00450218, 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/hal00450218}
} 
[2012,article] bibtexC. Banderier and P. Hitczenko, "Enumeration and asymptotics of restricted compositions having the same number of parts," Discrete Applied Mathematics, pp. 113, 2012.
@ARTICLE{banderier:hal00664192, 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 = {113},
note = {CALIN CALIN },
abstract = {{We study pairs and mtuples 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 Parisnord  LIPN , Departments of Mathematics and Computer Science},
audience = {internationale },
doi = {10.1016/j.dam.2011.12.011 },
hal_id = {hal00664192},
keywords = {Integer composition; Pairs of combinatorial structures; Local limit theorem; Asymptotics of Dfinite sequences; Diagonal of algebraic generating function},
language = {Anglais},
pdf = {http://hal.archivesouvertes.fr/hal00664192/PDF/BaHi.pdf},
url = {http://hal.archivesouvertes.fr/hal00664192}
} 
[2012,article] bibtexF. Bassino, A. Martino, C. Nicaud, E. Ventura, and P. Weil, "Statistical properties of subgroups of free groups," Random Structures and Algorithms, 2012.
@ARTICLE{bassino:hal00450218, 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 socalled wordbased distribution: subgroups are generated (finite presentations are determined) by randomly chosen ktuples 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 socalled graphbased 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 graphbased distribution, while they are exponentially generic in the wordbased 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 Parisnord  LIPN , School of Mathematics , Laboratoire d'Informatique GaspardMonge  LIGM , Department of Applied Mathematics III , Laboratoire Bordelais de Recherche en Informatique  LaBRI},
audience = {internationale },
hal_id = {hal00450218},
keywords = {subgroups of free groups; finite group presentations; statistical properties; Stallings graphs; partial injections; malnormality},
language = {Anglais},
pdf = {http://hal.archivesouvertes.fr/hal00450218/PDF/BMNVW.pdf},
url = {http://hal.archivesouvertes.fr/hal00450218}
} 
[2012,article] bibtexP. Clote, Y. Ponty, and J. Steyaert, "Expected distance between terminal nucleotides of RNA secondary structures.," Journal of Mathematical Biology, vol. 65, iss. 3, pp. 58199, 2012.
@ARTICLE{clote:inria00619921, author = {Clote, Peter and Ponty, Yann and Steyaert, JeanMarc},
title = {{Expected distance between terminal nucleotides of RNA secondary structures.}},
journal = {Journal of Mathematical Biology},
year = {2012},
volume = {65},
pages = {58199},
number = {3 },
month = Sep, note = {Digiteo Foundation and National Science Foundation grants DMS 0817971, DBI0543506 and DMS1016618. },
abstract = {{In "The ends of a large RNA molecule are necessarily close", Yoffe et al. (Nucleic Acids Res 39(1):292299, 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/s0028501104678 },
hal_id = {inria00619921},
language = {Anglais},
pdf = {http://hal.inria.fr/inria00619921/PDF/paper.pdf},
publisher = {Springer},
url = {http://hal.inria.fr/inria00619921}
} 
[2012,inproceedings] bibtexF. 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. 8899.
@INPROCEEDINGS{bassino:hal00678203, 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 = {8899},
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/hal00678203}
} 
[2012,inproceedings] bibtexF. 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. 155166.
@INPROCEEDINGS{bassino:hal00687981, 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 = {155166},
address = {Canada},
abstract = {{We consider a generalization of the uniform wordbased 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 wordbased 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 Parisnord  LIPN , Laboratoire d'Informatique GaspardMonge  LIGM , Laboratoire Bordelais de Recherche en Informatique  LaBRI},
audience = {internationale },
hal_id = {hal00687981},
language = {Anglais},
pdf = {http://hal.archivesouvertes.fr/hal00687981/PDF/BNWAofA.pdf},
url = {http://hal.archivesouvertes.fr/hal00687981}
} 
[2012,article] bibtexS. 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. 550562, 2012.
@ARTICLE{behrens:hal00793413, 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 = {550562},
number = {5},
owner = {Yawn},
timestamp = {2013.03.11},
url = {http://hal.inria.fr/hal00793413}
} 
[2011,inproceedings] bibtexG. 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:hal00587955, 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; peertopeer networks ; decentralized search; optimal paths},
owner = {Yawn},
timestamp = {2013.03.11},
url = {http://hal.inria.fr/hal00587955}
} 
[2011,inproceedings] bibtexY. 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:inria00601060, 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, basepair 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 fullfledged 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 = {inria00601060},
language = {Anglais},
pdf = {http://hal.inria.fr/inria00601060/PDF/BoltzmannEnsembleWithPK.pdf},
url = {http://hal.inria.fr/inria00601060}
} 
[2011,article] bibtexE. 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. 145150, 2011.
@ARTICLE{bertin:hal00744520, 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 = {145150},
number = {60},
month = Jun, owner = {Yawn},
timestamp = {2013.03.11},
url = {http://hal.inria.fr/hal00744520}
} 
[2011,inproceedings] bibtexF. 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. 207216.
@INPROCEEDINGS{pin:hal00788799, 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 = {207216},
address = {Paris, France},
publisher = {ICST},
owner = {Yawn},
timestamp = {2013.03.11},
url = {http://hal.inria.fr/hal00788799}
} 
[2011,inproceedings] bibtexO. Bodini, O. Roussel, and M. Soria, "Boltzmann samplers for firstorder differential specifications," in LAGOS 09 – V Latin – American Algorithms, Graphs and Optimization Symposium, Gramado, Brésil, 2011, p. 1.
@INPROCEEDINGS{bodini:hal00641072, author = {Bodini, Olivier and Roussel, Olivier and Soria, Michele},
title = {{Boltzmann samplers for firstorder 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/hal00641072}
} 
[2011,article] bibtexM. 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. 231244, 2011.
@ARTICLE{albert:hal00525425, 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 = {231244},
number = {2},
note = {11 pages},
owner = {Yawn},
timestamp = {2013.03.11},
url = {http://hal.inria.fr/hal00525425}
} 
[2011,inproceedings] bibtexP. Flajolet, M. Pelletier, and M. Soria, "On Buffon Machines and Numbers," in Proceedings of the 22nd Annual ACMSIAM Symposium on Discrete Algorithms (SODA), San Francisco, ÉtatsUnis, 2011, p. pp. 172183.
@INPROCEEDINGS{flajolet:hal00548904, author = {Flajolet, Philippe and Pelletier, Maryse and Soria, Mich{\`e}le},
title = {{On Buffon Machines and Numbers}},
booktitle = {{Proceedings of the 22nd Annual ACMSIAM Symposium on Discrete Algorithms (SODA)}},
year = {2011},
pages = {pp. 172183},
address = {San Francisco, {\'E}tatsUnis},
note = {Largely revised version with references and figures added. 12 pages. },
abstract = {{The wellknow 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 logarithmicseries distributions. We provide humanaccessible 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 = {hal00548904},
language = {Anglais},
pdf = {http://hal.archivesouvertes.fr/hal00548904/PDF/0906.5560v2.pdf},
url = {http://hal.archivesouvertes.fr/hal00548904}
} 
[2011,inproceedings] bibtexP. Héam and C. Nicaud, "Seed, an EasytoUse 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. 6069.
@INPROCEEDINGS{heam:hal00620373, author = {H{\'e}am, PierreCyrille and Nicaud, Cyril},
title = {{Seed, an EasytoUse 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/hal00620373}
} 
[2011,techreport] bibtexA. Wieczorek, A. Busic, and E. Hyon, "Critical level policies in lost sales inventory systems with different demand classes," INRIA, Rapport de recherche RR7732, 2011.
@TECHREPORT{wieczorek:inria00620243, 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 = {RR7732},
month = Sep, keywords = {Markov decision process; Critical level policies; Inventory systems},
owner = {Yawn},
timestamp = {2013.03.11},
url = {http://hal.inria.fr/inria00620243}
} 
[2011,inproceedings] bibtexS. Janssen, Y. Ponty, B. Raman, S. Sheikh, J. Steyaert, and P. Clote, "Investigating the RFAM paradox: The pseudoknot explanation," in Fifth IndoFrench Bioinformatics Meeting, Hyderabad, Inde, 2011.
@INPROCEEDINGS{janssen:hal00585647, author = {Janssen, Stefan and Ponty, Yann and Raman, Balaji and Sheikh, Saad and Steyaert, JeanMarc and Clote, Peter},
title = {{Investigating the RFAM paradox: The pseudoknot explanation}},
booktitle = {{Fifth IndoFrench Bioinformatics Meeting}},
year = {2011},
address = {Hyderabad, Inde},
month = Mar, note = {Short abstract},
owner = {Yawn},
timestamp = {2013.03.11},
url = {http://hal.inria.fr/hal00585647}
} 
[2011,article] bibtexF. Bassino, M. Bouvel, and D. Rossin, "Enumeration of PinPermutations," Electronic Journal of Combinatorics, vol. 18, iss. 1, p. 57, 2011.
@ARTICLE{bassino:hal00348664, author = {Bassino, Fr{\'e}d{\'e}rique and Bouvel, Mathilde and Rossin, Dominique},
title = {{Enumeration of PinPermutations}},
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/hal00348664}
} 
[2011,article] bibtexM. Bouvel, C. Chauve, M. Mishna, and D. Rossin, "Averagecase analysis of perfect sorting by reversals," Discrete Mathematics, Algorithms and Applications, vol. 3, iss. 3, pp. 369392, 2011.
@ARTICLE{bouvel:hal00649761, author = {Bouvel, Mathilde and Chauve, C{\'e}dric and Mishna, Marni and Rossin, Dominique},
title = {{Averagecase analysis of perfect sorting by reversals}},
journal = {Discrete Mathematics, Algorithms and Applications},
year = {2011},
volume = {3},
pages = {369392},
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 runtime 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. 314325, 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 = {hal00649761},
keywords = {Algorithm analysis ; genome rearrangements ; tree parameters ; simple permutations},
language = {Anglais},
pdf = {http://hal.archivesouvertes.fr/hal00649761/PDF/BoChMiRo\_HAL.pdf},
url = {http://hal.archivesouvertes.fr/hal00649761}
} 
[2011,inproceedings] bibtexC. Banderier and P. Nicodeme, "Constant time estimation of ranking statistics by analytic combinatorics," in Statistical Methods for PostGenomic Data, Paris, France, 2011, p. i.
@INPROCEEDINGS{banderier:hal00567091, author = {Banderier, Cyril and Nicodeme, Pierre},
title = {{Constant time estimation of ranking statistics by analytic combinatorics}},
booktitle = {{Statistical Methods for PostGenomic 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/hal00567091}
} 
[2011,article] bibtexJ. 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. 146579, 2011.
@ARTICLE{waldispuhl:hal00681928, 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 = {146579},
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 sequencestructure relationship. We recently introduced a suite of algorithms called RNAmutants which allows a complete exploration of RNA sequencestructure maps in polynomial time and space. Formally, RNAmutants takes an input sequence (or seed) to compute the Boltzmannweighted 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+Ccontents. 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+Ccontents. 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+Ccontent has a strong influence on the size and shape of the evolutionary accessible sequence and structural spaces. In particular, we show that low G+Ccontents favor the apparition of internal loops and thus possibly the synthesis of tertiary structure motifs. On the other hand, high G+Ccontents 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 = {hal00681928},
language = {Anglais},
publisher = {Mary Ann Liebert},
url = {http://hal.inria.fr/hal00681928}
} 
[2011,inproceedings] bibtexJ. 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. 501515.
@INPROCEEDINGS{waldispuhl:hal00546847, 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 = {501515},
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 sequencestructure relationship. We recently introduced a suite of algorithms called RNAmutants which allows, for the rst time, a complete exploration of RNA sequencestructure 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+Ccontents. 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+Ccontents. 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+Ccontent 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+Ccontents favor the apparition of internal loops and thus possibly the synthesis of tertiary structure motifs. On the other hand, high G+Ccontents 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/9783642200366\_45 },
hal_id = {hal00546847},
language = {Anglais},
pdf = {http://hal.archivesouvertes.fr/hal00546847/PDF/paper.pdf},
url = {http://hal.archivesouvertes.fr/hal00546847}
} 
[2011,article] bibtexB. Chauvin, B. Salvy, M. Soria, and B. Vallee, "Philippe Flajolet, le fondateur de la combinatoire analytique," La gazette des mathématiciens, vol. 129, pp. 113114, 2011.
@ARTICLE{chauvin:hal00680928, 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 = {113114},
month = Jul, owner = {Yawn},
timestamp = {2013.03.11},
url = {http://hal.inria.fr/hal00680928}
} 
[2011,article] bibtexT. Zuliani, J. David, S. Bercegeay, M. Pandolfino, I. RoddeAstier, 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 gaspermeable bag: interests for adoptive immunotherapy.," Journal of Translational Medicine, vol. 9, iss. 1, p. 63, 2011.
@ARTICLE{zuliani:inserm00663657, author = {Zuliani, Thomas and David, Julien and Bercegeay, Sylvain and Pandolfino, MarieChristine and RoddeAstier, 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 gaspermeable bag: interests for adoptive immunotherapy.}},
journal = {{Journal of Translational Medicine}},
year = {2011},
volume = {9},
pages = {63},
number = {1},
doi = {10.1186/14795876963},
owner = {Yawn},
timestamp = {2013.03.11},
url = {http://hal.inria.fr/inserm00663657}
} 
[2010,article] bibtexA. Denise, Y. Ponty, and M. Termier, "Controlled non uniform random generation of decomposable structures," Journal of Theoretical Computer Science (TCS), vol. 411, iss. 4042, pp. 35273552, 2010.
@ARTICLE{denise:hal00483581, 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 = {35273552},
number = {4042 },
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 realvalued 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 contextfree 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 = {hal00483581},
keywords = {G.2.1 G.2.1},
language = {Anglais},
pdf = {http://hal.archivesouvertes.fr/hal00483581/PDF/NonUniform2009.pdf},
url = {http://hal.archivesouvertes.fr/hal00483581}
}
Ancienne liste

[2012,inproceedings] bibtexM. 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] bibtexF. 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] bibtexF. 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] bibtexO. Ait Mous, F. Bassino, and C. Nicaud, "An efficient linear pseudominimization algorithm for AhoCorasick automata," in 23rd Annual Symposium on Combinatorial Pattern Matching (CPM 2012), Helsinki, Finland, 2012, pp. 110123.
@InProceedings{abn12c, author = {Ait Mous, Omar and Bassino, Fr{\'e}d{\'e}rique and Nicaud, Cyril},
title = {An efficient linear pseudominimization algorithm for {A}ho{C}orasick automata},
booktitle = {23rd Annual Symposium on Combinatorial Pattern Matching (CPM 2012)},
pages = {110123},
year = 2012, volume = {7354},
series = {Lecture Notes in Computer Science},
address = {Helsinki, Finland},
month = {July},
publisher = {Springer}
} 
[2012,inproceedings] bibtexJ. 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{DUBOISBERRANGER2012666399, hal_id = {hal00666399},
url = {http://hal.inria.fr/hal00666399},
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 nonuniform 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 wellsuited 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 stepbystep 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 Contextfree 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/hal00666399/PDF/WordCollectorDanieleJeremieYann2012.pdf},
} 
[2012,inproceedings] bibtexB. Morcrette, "Fully analyzing an algebraic Pólya urn model," in LATIN 2012, 2012, pp. 568581.
@inproceedings{Morcrette2012, year = {2012},
author = {Morcrette, Basile},
title = {Fully analyzing an algebraic {P}\'olya urn model},
booktitle = {LATIN 2012},
series = {LNCS},
volume= {7256},
pages = {568581},
Note = {To appear, April 2012}
} 
[2012,inproceedings] bibtexJ. 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:hal00666399, hal_id = {hal00666399},
url = {http://hal.inria.fr/hal00666399},
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 Contextfree 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/hal00666399/PDF/WordCollectorDanieleJeremieYann2012.pdf},
} 
[2012,article] bibtexF. Bassino, J. David, and C. Nicaud, "Average Case Analysis of Moore’s State Minimization Algorithm," Algorithmica, vol. 63, iss. 1–2, pp. 509531, 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 = {12},
pages = {509531}
} 
[2012,article] bibtexF. 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] bibtexP. Rinaudo, Y. Ponty, D. Barth, and A. Denise, "Tree decomposition and parameterized algorithms for RNA structuresequence alignment including tertiary interactions and pseudoknots," in WABI – 12th Workshop on Algorithms in Bioinformatics – 2012, Ljubljana, Slovenia, 2012.
@inproceedings{rinaudo:hal00708580, hal_id = {hal00708580},
url = {http://hal.inria.fr/hal00708580},
title = {{Tree decomposition and parameterized algorithms for RNA structuresequence alignment including tertiary interactions and pseudoknots}},
author = {Rinaudo, Philippe and Ponty, Yann and Barth, Dominique and Denise, Alain},
keywords = {RNA structure; sequencestructure alignment; treedecomposition},
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/hal00708580/PDF/article.pdf},
} 
[2012,inproceedings] bibtexB. 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] bibtexC. 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. 107116.
@inproceedings{BANDERIER2012643598, hal_id = {hal00643598},
url = {http://hal.archivesouvertes.fr/hal00643598},
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, powerlaw 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 Parisnord  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 = {107116},
address = {Kyoto, Japon},
audience = {internationale },
year = {2012},
pdf = {http://hal.archivesouvertes.fr/hal00643598/PDF/analco\_soda.pdf},
} 
[2012,article] bibtexX. Wang, M. Latapy, and M. Soria, "Deciding on the type of the degree distribution of a graph from traceroutelike measurements," IJCNC/IJDPS, p. 1, 2012.
@ARTICLE{LIP68105, author = {Wang, Xiaomin and Latapy, Matthieu and Soria, Mich{\`{e}}le},
xlip6teams = {APR, COMPLEXNETWORKS},
xlip6id = {8105},
xinternationalaudience = {yes},
title = {Deciding on the type of the degree distribution of a graph from traceroutelike measurements},
journal = {IJCNC/IJDPS},
year = {2012},
pages = {1, 20},
note = {To appear}
} 
[2012,inproceedings] bibtexS. 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:hal00670232, hal_id = {hal00670232},
url = {http://hal.inria.fr/hal00670232},
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 , AlbertLudwigs University  ALBERTLUDWIGS 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/hal00670232/PDF/NPCompletenessStacking.pdf},
} 
[2012,inproceedings] bibtexF. 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. 155166.
@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 = {155166},
year = 2012, volume = {},
series = {Discrete Mathematics \& Theoretical Computer Science Proceedings},
address = {Montr{\'e}al, Canada},
month = {June},
note={12 pages}
} 
[2012,inproceedings] bibtexP. 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 NonClassical Models of Automata and Applications, Aug. 2012, Fribourg, Switzerland, 18 pages}
} 
[2012,inproceedings] bibtexA. 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. 109120.
@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 = {109120},
series = {Lecture Notes in Computer Science},
ISBN = {},
ISSN = {},
year = {2012},
volume = {},
editor = {David Fern\`andezBaca},
publisher = {SpringerVerlag},
address = {Berlin, Heidelberg},
URL = {},
URN = {},
doi = {},
annote = {Keywords: cellular automata, interacting particle systems, density classification, percolation}
} 
[2012,article] bibtexC. Pivoteau, B. Salvy, and M. Soria, "Algorithms for combinatorial structures: Wellfounded 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},
xlip6teams = {APR},
xlip6id = {4891},
xinternationalaudience = {yes},
title = {Algorithms for combinatorial structures: Wellfounded systems and Newton iterations},
journal = {Journal of Combinatorial Theory, Series A (JCTA)},
volume = {119},
year = {2012},
pages = {1711–1773}
} 
[2012,article] bibtexO. Bodini, O. Roussel, and M. Soria, "Boltzmann samplers for first order combinatorial differential equations," Discrete Applied Mathematics, pp. 117 to appear, 2012.
@ARTICLE{LIP64256, author = {Bodini, Olivier and Roussel, Olivier and Soria, Mich{\`{e}}le},
xlip6teams = {APR},
xlip6id = {4256},
xinternationalaudience = {yes},
title = {Boltzmann samplers for first order combinatorial differential equations},
journal = {Discrete Applied Mathematics},
year = {2012},
pages = {117 to appear},
labs={LIP6},
teams={APR},
pub_status={INT},
} 
[2012,inproceedings] bibtexO. 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. 92106.
@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 = {92106},
year = {2012},
month = {January},
publisher = {SIAM}
} 
[2012,inproceedings] bibtexF. 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.stacsconf.org},
} 
[2012,article] bibtexA. 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. 112, 2012.
@ARTICLE{LIP65601, author = {Darrasse, Alexis and Panagiotou, Konstantinos and Roussel, Olivier and Soria, Mich{\`{e}}le},
xlip6teams = {APR},
xlip6id = {5601},
xinternationalaudience = {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 = {112}
} 
[2011,inproceedings] bibtexJ. 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. 501515.
@inproceedings{waldispuhl:hal00546847, hal_id = {hal00546847},
url = {http://hal.archivesouvertes.fr/hal00546847},
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 = {501515},
address = {Vancouver, Canada},
volume = {6577},
editor = {Bafna, Vineet and Sahinalp, S. },
series = {Lecture Notes in Computer Science },
audience = {international },
doi = {10.1007/9783642200366\_45 },
year = {2011},
pdf = {http://hal.archivesouvertes.fr/hal00546847/PDF/paper.pdf},
} 
[2011,inproceedings] bibtexP. Flajolet, M. Pelletier, and M. Soria, "On Buffon Machines and Numbers," in SODA’11, 2011, p. pp. 172183.
@INPROCEEDINGS{LIP64277, author = {Flajolet, Philippe and Pelletier, Maryse and Soria, Mich{\`{e}}le},
xlip6teams = {APR},
xlip6id = {4277},
xinternationalaudience = {yes},
title = {On Buffon Machines and Numbers},
booktitle = {SODA'11},
year = {2011},
pages = {pp. 172183},
location = {San Francisco {\'{E}}tatsUnis},
url = {http://hal.archivesouvertes.fr/hal00548904/en/},
labs={LIP6},
teams={APR},
pub_status={INT},
} 
[2011,inproceedings] bibtexY. 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:inria00601060, hal_id = {inria00601060},
url = {http://hal.inria.fr/inria00601060},
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/inria00601060/PDF/BoltzmannEnsembleWithPK.pdf},
} 
[2011,inproceedings] bibtexG. Giakkoupis and N. Schabanel, "Optimal Path Search in Small Worlds: Dimension Matters," in Proc of ACM Symp. on Theory of Computing (STOC), 2011, pp. 393402.
@inproceedings{GiakkoupisSchabanel2010STOC, Author = {George Giakkoupis and Nicolas Schabanel},
Booktitle = {Proc of ACM Symp. on Theory of Computing (STOC)},
Pages = {393402},
Title = {Optimal Path Search in Small Worlds: Dimension Matters},
Volume = {43},
Year = {2011}
} 
[2011,inproceedings] bibtexJ. Mairesse, A. Micheli, and D. Poulalhon, "Minimizing braids on four strands," in Braids, 2011.
@InProceedings{mmp11a, keywords = {ccom},
author = {J. Mairesse and A. Micheli and D. Poulalhon},
title = {Minimizing braids on four strands},
booktitle = {Braids},
year = 2011 } 
[2011,misc] bibtexN. 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] bibtexN. 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] bibtexF. Bassino, M. Bouvel, and D. Rossin, "Enumeration of pinpermutations," 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 pinpermutations},
journal = {Electronic Journal of Combinatorics},
year = {2011},
volume = {18},
issue = {1},
annote = {paper P.57}
} 
[2011,article] bibtexM. Bouvel, C. Chauve, M. Mishna, and D. Rossin, "Averagecase 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 = {Averagecase analysis of perfect sorting by reversals},
journal = {Discrete Mathematics, Algorithms and Applications},
year = {2011},
volume = {3},
number = {3},
} 
[2011,article] bibtexF. Bassino, M. Bouvel, and D. Rossin, "Enumeration of PinPermutations," 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 PinPermutations},
journal = {Electronic Journal of Combinatorics},
year = {2011},
volume = {18},
number = {1},
note = {Paper P57},
} 
[2011,inproceedings] bibtexJ. Mairesse, A. Micheli, and D. Poulalhon, "Comment minimiser une tresse," in Journées de Combinatoire de Bordeaux, 2011.
@InProceedings{mmp11b, keywords = {ccom},
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] bibtexA. 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. 296307.
@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 = {296307},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897255},
ISSN = {18688969},
year = {2011},
volume = {9},
editor = {Thomas Schwentick and Christoph D{\"u}rr},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2011/3019},
URN = {urn:nbn:de:0030drops30190},
doi = {http://dx.doi.org/10.4230/LIPIcs.STACS.2011.296},
annote = {Keywords: probabilistic cellular automata, perfect sampling, ergodicity}
} 
[2011,article] bibtexP. Clote, Y. Ponty, and J. Steyaert, "Expected distance between terminal nucleotides of RNA secondary structures," Journal of Mathematical Biology, pp. 119, 2011.
@article{clote:inria00619921, hal_id = {inria00619921},
url = {http://hal.inria.fr/inria00619921},
title = {{Expected distance between terminal nucleotides of RNA secondary structures}},
author = {Clote, Peter and Ponty, Yann and Steyaert, JeanMarc},
language = {English},
affiliation = {Laboratoire d'informatique de l'{\'e}cole polytechnique  LIX , Department of Biology , AMIB  INRIA Saclay  Ile de France},
publisher = {Springer},
pages = {119},
journal = {Journal of Mathematical Biology},
audience = {international },
year = {2011},
pdf = {http://hal.inria.fr/inria00619921/PDF/paper.pdf},
} 
[2011,article] bibtexJ. 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. 146579, 2011.
@article{waldispuhl:hal00681928, hal_id = {hal00681928},
url = {http://hal.inria.fr/hal00681928},
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 = {146579},
journal = {Journal of Computational Biology},
volume = {18},
number = {11 },
audience = {international },
doi = {10.1089/cmb.2011.0181 },
year = {2011},
month = Nov, } 
[2010,article] bibtexF. Bassino, M. Bouvel, A. Pierrot, and D. Rossin, "Deciding the finiteness of the number of simple permutations contained in a wreathclosed 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 wreathclosed class is polynomial},
journal = {Pure Mathematics and Applications},
year = {2010},
volume = {21},
number = {2},
} 
[2010,article] bibtexF. Bassino, M. Bouvel, A. Pierrot, and D. Rossin, "Deciding the finiteness of simple permutations contained in a wreathclosed class is polynomial," Pure Mathematics and Applications, vol. 21, iss. 2, pp. 119135, 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 wreathclosed class is polynomial},
journal = {Pure Mathematics and Applications},
year = {2010},
volume = {21},
number = {2},
pages = {119135},
}