Gwenaël Richomme

Publications

Dernière modification de cette page d'accueil (d'autres pages du site peuvent avoir été modifiées depuis) : 11 mars 2012

Rubriques : Accueil Publications Enseignements Responsabilités

Ouvrages édités

F. Durand, G. Richomme, Numéro spécial de la revue RAIRO Informatique Théorique et Applications, dédié à la conférence Journées Montoises d'Informatique Théorique (Amiens, septembre 2010), janvier 2012 (13 articles acceptés sur 19 soumis).
G. Richomme (éd.). Numéro spécial de la revue RAIRO Informatique Théorique et Applications, dédié au Workshop on Word Avoidability, Complexity and Morphisms, vol 40-3, p. 405-484, 2006.
G. Richomme (éd.) Actes du Workshop on Word Avoidability, Complexity and Morphisms (manifestation satellite de ICALP'2004, 54 pages, rapport interne 2004-07 du LaRIA.

Articles en revues

G. Richomme, P. Séébold, Completing a Combinatorial Proof of the Rigidity of Sturmian Words Generated by Morphisms, Theoretical Computer Science 428, 92-97, 2012 (doi). Voir aussi : rapport interne RR-10030 du LIRMM (déposé sur HAL-LIRMM) .
G. Richomme, P. Séébold, On factorially balanced sets of words, Theoretical Computer Science 412, 5492-5497, 2011 (doi). Voir aussi rapport interne RR-10028 du LIRMM (déposé sur HAL-LIRMM) .
J. Cassaigne, G. Richomme, K. Saari, L.Q. Zamboni, Avoiding Abelian powers in binary words with bounded Abelian complexity, International Journal of Foundations of Computer Science 22(4), 905-920, 2011 (pré-publication arXiv:1005.2514v1, doi).
G. Richomme, K. Saari, L.Q. Zamboni, Abelian Complexity in Minimal subshifts, Journal of the London Mathematical Society 83(1), 79-95, 2011 (pré-publication arXiv:0911.2914v1, doi).
D. Jamet, G. Paquin, G. Richomme, L. Vuillon, On the fixed points of the iterated pseudopalindromic closure, Theoretical Computer Science 412, Issue 27, 2974-2987, 2011, special issue "Combinatorics on Words (WORDS 2009), 7th International Conference on Words" (doi ; pré-publication arXiv:0904.3828v1).
R. Groult, E. Prieur, G. Richomme, Counting distinct palindromes in a word in linear time, Information Processing Letters 110, issue 20, 908-912, 2010 (doi).
R. Groult, G. Richomme, Optimality of some algorithms to detect quasiperiodicities, Theoretical Computer Science 411, issues 34-36, 3110-3122, 2010. (doi).
G. Richomme, K. Saari, L.Q. Zamboni, Balance and Abelian Complexity of the Tribonacci Word, Advance Applied Mathematics 45, 212-231, 2010 (doi ; pré-publication arXiv:0904.2872v1).
G. Richomme, K. Saari, L.Q. Zamboni, Standard Factors of Sturmian Words, RAIRO Theoretical Informatics and Applications 44(1), numéro spécial de la revue dédié à la conférence "Journées Montoises d'Informatique Théorique 2008", 159-174, 2010.
A. Glen, F. Levé, G. Richomme, Directive words of episturmian words: equivalences and normalization, RAIRO Theoretical Informatics and Applications 43, p. 299-319, 2009 (doi ; pré-publication arxiv:0802.3888v1).
A. Glen, F. Levé, G. Richomme, Quasiperiodic and Lyndon episturmian words, Theoretical Computer Science 409(3), pages 578-600, 2008 (doi). (voir aussi arxiv)
G. Richomme, SudoLyndon (pdf), Bulletin of the European Association of Theoretical Computer Science 92, p143-149, 2007 (solutions des grilles : pdf) (Voir aussi rapport interne 2007-02 du LaRIA, HAL et arxiv).
G. Richomme, F. Wlazinski, Existence of finite test-sets for k-power-freeness of uniform morphisms (version étendue de l'article présenté à WOWA'2006), Discrete Applied Mathematics 155(15), p2001-2016, 2007 (doi).
G. Richomme, Conjugacy of morphisms and Lyndon decomposition of standard Sturmian words, Theoretical Computer Science 380, numéro spécial Words'2005, p393-400, 2007 (doi).
F. D'Alessandro, G. Richomme,S. Varrichio, Well quasi-orders generated by a word-shuffle rewriting, (version étendue de l'article accepté à DLT'06), Theoretical Computer Science 377, 73-92, 2007 (doi).
Cet article a fait l'objet du rapport interne 2006-06 du LaRIA déposé sur HAL et arxiv.
F. Levé, G. Richomme, Quasiperiodic Sturmian words and morphisms, Theoretical Computer schemeience 372(1), p15-25, 2007 (doi).
Cet article a fait l'objet du rapport interne 2006-01 du LaRIA, déposé sur HAL et arxiv).
G. Richomme, On morphisms preserving infinite Lyndon words, Discrete Mathematics and Theoretical Computer Science 9(2), numéro spécial "Journées Montoises d'Informatique Théorique", p89-108, 2007 (lien, version préliminaire au format .ps.gz)
F. Levé, G. Richomme, On a conjecture about finite fixed points of morphisms, Theoretical Computer Science 339 (1), p103-128, 2005. (voir www.sciencedirect.com).
F. Levé, G. Richomme, Quasiperiodic infinite words: some anwers, Bulletin of the European Association for Theoretical Computer Science 84, p128-138, 2004. (pdf, erratum)
S. Fossé, G. Richomme, Some characterizations of Parikh matrix equivalent binary words, Information Processing Letters, 92(2), p77-82, 2004.
G. Richomme, F. Wlazinski, Overlap-free morphisms and finite test-sets, Discrete Applied Mathematics 143(1-3), p92-109, 2004. (plus d'info)
G. Richomme, P. Séébold, Conjectures and results on morphisms generating k-power-free words, International Journal of Foundations of Computer Science, 15 (2) (Special issue Combinatorics on words), p307-316, 2004.
G. Richomme, Some algorithms to compute the conjugates of episturmian morphisms, RAIRO Theoretical Informatics and Applications, 37, p85-104, 2003.
G. Richomme, Lyndon morphisms, Bulletin of the Belgian Mathematical Society 10(5), p761-785, 2003. (numéro spécial "Journées Montoises d'Informatique Théorique")( Accès à la publication).
Ici le résumé paru dans les Actes de la 9-ème Conférence Internationale Journées Montoises d'Informatique théorique, 9-11 septembre 2002, Montpellier, France.
G. Richomme, Conjugacy and episturmian morphisms, Theoretical Computer Science 302, p1-34, 2003. (plus d'info)
Aussi Présenté à la conférence WORDS'2001, Palermo, Italy.
G. Richomme, Some non finitely generated monoids of repetition-free endomorphisms, Information Processing Letters 85(2), p61-66, 2003. (plus d'info)
G. Richomme, F. Wlazinski, Some results on k-power-free morphisms, Theoretical Computer Science 273, p119-142, 2002. (plus d'info)
D. Kirsten, G. Richomme, Decidability equivalence between the star problem and the finite power problem in trace monoids, Theory of Computing Systems 34, p193-227, 2001. (plus d'info)
G. Richomme, P. Séébold, Characterization of test-sets for overlap-free morphisms, Discrete Applied Mathematics 98, p151-157, 1999. (plus d'info)
G. Richomme, Test-words for sturmian morphisms, Bulletin of the Belgian Mathematical Society 6, p481-489, 1999. (plus d'info, accès à la publication)
G. Richomme, Another characterization of sturmian words, Bulletin of the European Association for Theoretical Computer Science, vol 67, p173-175, February 1999. (plus d'info)
G. Richomme, Y. Métivier, New results on the star problem in trace monoids, Information and Computation 119(2), p240-251, 1995. (plus d'info)

Conférences et exposés

F. Durand, G. Richomme, J. Leroy, Some examples and counter-examples about the S-adic conjecture, Numération 2011, Liège, 6-10 juin 2011.
R. Groult, E. Prieur, G. Richomme, Counting different palindromes in a word in linear time, Journées GTseq, "Algorithmique, combinatoire du texte et applications en bio-informatique", organisées conjointement par l'axe "analyse de séquences" du GDR Bio-Informatique Moléculaire (3003) et le groupe de travail COMATEGE du GDR Informatique Mathématique, 25-26 janvier 2010.
G. Richomme, K. Saari, L.Q. Zamboni, Abelian Properties of Words (Extended abstract), actes (CDROM) de WORDS'2009, Salerno, Italy, septembre 2009.
D. Jamet, G. Paquin, G. Richomme, L. Vuillon, On the fixed points of the iterated pseudopalindromic closure, actes (CDROM) de WORDS'2009, Salerno, Italy, septembre 2009.
Aussi présenté à CanaDAM 2009, 2nd Canadian Discrete and Algorithmic Mathematics Conference, Montreal, Canada (2009) (voir fiche HAL).
R. Groult, G. Richomme, Optimality of some algorithms to detect maximal quasiperiodicities, JORCAD'08, "Journées Rouennaises de Combinatoire et Algorithmique en l'honneur de J.P. Duval" et Journées annuelles nationales des groupes de travail CoMaTeGe et SDA2 du GDR IM du CNRS, Rouen, 17-19 septembre 2008, actes locaux. (2 pages)
G. Richomme, Quasiperiodic words, exposé invité à JM'08, 12-ème Conférence Internationale "Journées Montoises d'Informatique Théorique", 27-30 août 2008, Mons, Belgique, actes locaux.
A. Glen, F. Levé, G. Richomme, Directive words of episturmian words (voir arxiv:0802.3888v1), actes locaux de JM'08.
K. Saari, G. Richomme, L. Q. Zamboni, Standard Words and Abelian Powers in Sturmian Words, actes locaux de JM'08.
F. Levé, G. Richomme, Quasiperiodic episturmian words, actes de Words'2007, Marseille, France, septembre 2007.
G. Richomme, A local balance property of episturmian words, Proceedings of Development in Language Theory (DLT'2007), 11th International Conference, 3-6 juillet, Turku, Finlande, Lecture Notes in Computer Sicence 4588, p371-381, 2007.
Cet article a fait l'objet d'un rapport interne 2007-02 du LaRIA (voir HAL et arxiv)
F. D'Alessandro, G. Richomme, S. Varrichio, Well quasi orders and the shuffle closure of finite sets, actes de la conférence DLT'2006 (Development in Language Theory), 26-29 juin 2006, Santa Barbara (California), USA, Lecture Notes in Computer Science 4036 (2006), p260-269.
G. Richomme, F. Wlazinski, Existence of finite test-sets for k-power-freeness of uniform morphisms, actes de WOWA'2006, Workshop on Words and Automata (événement satellite de la conférence CSSR'06 - International Computer Science Symposium in Russia), 7 juin 2006, St Petersburg, Russie, actes sur CD. (rapport interne 2005-10 du LaRIA, déposé sur HAL et arxiv)
G. Richomme, Conjugacy of morphisms and Lyndon decomposition of standard Sturmian words, actes de Words 2005, 5th international conference on words, 13-15 septembre2005, Montréal, publications du LaCIM (Laboratoire de Combinatoire et d'Informatique Mathématique), numéro 36, page 341-351 (S. Brlek, C. Reutenauer eds.).
Transparents de l'exposé (pdf).
Cet article a fait l'objet du rapport interne 2005-09 du LaRIA et d'un dépot sur HAL (voir ici).
G. Richomme, On morphisms preserving infinite Lyndon words (extended abstract), actes de la 10ème conférence internationale "Journées Montoises d'Informatique Théorique", 8-11 septembre 2004, Liège (Belgique), prépublication 04.006 de l'Institut de Mathématiques, Université de Liège, pages 325-333. (ps.gz)
Exposé invité à Ecole Jeunes Chercheurs en Algorithmique et Calcul Formel : Morphismes et mots sans répétitions (version ps.gz (légèrement corrigée) des transparents figurant dans les actes), 31 mars-4avril 2003.
F. Levé, G. Richomme, On a conjecture about finite fixed points of morphisms (extended abstract), proceedings of WORDS'03 4th International Conference on Combinatorics on Words, Turku (Finlande), Turku Centre for Computer Science General Publications No 27 (August 2003), p198-206. (ps.gz)
G. Richomme, F. Wlazinski, Finite test-sets for overlap-free morphisms, in K. Diks and W. Rytter (editors), MFCS'2002, vol. 2420 of Lecture Notes in Computer Science, pages 605-614, 2002. (plus d'info)
Résumé étendu de l'article Overlap-free morphisms and finite test-sets.
G. Richomme, F. Wlazinski, About cube-free morphisms, in H. Reichel and S. Tison, editors, STACS'2000, vol. 1770 of Lecture Notes in Computer Science, p99-109, 2000. (plus d'info)
Résumé étendu de Some results on k-power-free morphisms.
G. Richomme, Y. Métivier, P.A. Wacrenier, Computing the closure of sets of words under partial commutations, in Z. Fulöp and F. Gécseg (editors), ICALP'95, vol. 974 of Lecture Notes in Computer Science, p75-86. Springer Verlag, 1995. (plus d'info)
G. Richomme, Some trace monoids where both the star problem and the finite power problem are decidable, in I. Prívara, B. Rovan, and Ruzicka (editors), MFCS'94, vol. 841 of Lecture Notes in Computer Science, p577-586. Springer Verlag, 1994. (plus d'info)
G. Richomme, Y. Métivier, On the star operation and the finite power property in free partially commutative monoids, in P. Enjalbert, E.W. Mayr, and K.W. Wagner (editors), STACS'94, vol. 775 of Lecture Notes in Computer Science, p341-352. Springer Verlag, 1994. (plus d'info)
Résumé étendu de l'article New results on the star problem in trace monoids.

Mémoire d'habilitation (février 2004)

Contribution à la combinatoire des mots : traces et morphismes (ps.gz, remarque).