74 citations
- Laboratoire d'Informatique Gaspard-MongeFR20 papers
- Université Gustave EiffelFR8 papers
- Laboratoire d'Informatique, Signaux et Systèmes de Sophia AntipolisFR2 papers
- Laboratoire Traitement et Communication de l’InformationFR2 papers
- Disco (Germany)DE1 paper
- Institut Camille JordanFR1 paper
- Institut de Mathématiques de MarseilleFR1 paper
- Instituto de Gastroenterologia de GoiâniaBR1 paper
- International Center for Transitional JusticeUS1 paper
- Laboratoire Bordelais de Recherche en InformatiqueFR1 paper
- Laboratoire d'Astrophysique de BordeauxFR1 paper
- Laboratoire de Physique ThéoriqueFR1 paper
Showing cs.DSShow all
3 papers · 1 filter
cs.DS2009★ 1 cited
On the Average Complexity of Moore's State Minimization Algorithm
Frédérique Bassino, Julien David, Cyril Nicaud
We prove that, for any arbitrary finite alphabet and for the uniform distribution over deterministic and accessible automata with n states, the average complexity of Moore's state…
cs.DS2008★ 1 cited
Comparing RNA structures using a full set of biologically relevant edit operations is intractable
Guillaume Blin, Sylvie Hamel, Stéphane Vialette
Arc-annotated sequences are useful for representing structural information of RNAs and have been extensively used for comparing RNA structures in both terms of sequence and structu…
cs.DS2008
Understanding maximal repetitions in strings
Maxime Crochemore, Lucian Ilie
The cornerstone of any algorithm computing all repetitions in a string of length n in O(n) time is the fact that the number of runs (or maximal repetitions) is O(n). We give a simp…