Gwenaël Richomme

Publications

Dernière modification de cette page : 3 mars 2023

Rubriques : Accueil Publications Enseignements Responsabilités

DBLP, HAL, arxiv, ORCID

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, On sets of indefinitely desubstitutable words, Theoretical Computer Science 857, 97-113, 2021 (doi, preprint arxiv, preprint hal)
G. Gamard, G. Richomme, Coverability and Multi-scale Coverability on Infinite Pictures,Journal of Computer and System Sciences 104, 258-277, 2019 (doi). (titre initial : Comparison of Coverability and Multi-Scale Coverability in One and Two Dimensions, preprint on arxiv)
G. Richomme, Characterization of infinite LSP words and endomorphisms preserving the LSP property, International Journal of Foundations of Computer Science, Vol. 30, No. 1, 171-196, 2019 (arxiv, HAL).
M. Bucci, G. Richomme, Greedy palindromic lengths, International Journal of Foundations of Computer Science, Vol 29, No. 3, 331-356, 2018 (doi, preprint on arxiv).
G. Gamard, P. Ochem, G. Richomme, P. Séébold, Avoidability of circular formulas, Theoretical Computer Science 726, p1-4, 2018 (doi, preprint sur arxiv).
G. Gamard, G. Richomme, J. Shallit, T. J. Smith, Periodicity in Rectangular Arrays, Information Processing Letters 118 (2017), 58-63 (doi, publication en ligne : 30 septembre 2016, ) (preprint on arxiv, 2016).
G. Richomme, Minimal critical exponent of quasiperiodic words, Theoretical Computer Science 548, 117-122, 2014 (doi).
F. Durand, J. Leroy, G. Richomme, Do the Properties of an S-adic Representation Determine Factor Complexity?, Journal of Integer Sequences, vol 16, Article 13.2.6, 2013.
J. Leroy, G. Richomme, A combinatorial proof of S-adicity for sequences with linear complexity, INTEGERS, vol 13, Article #A5, 2013.
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 Science 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 (DMTCS, Fiche HAL avec article en pdf)
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 answers, 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

G. Richomme, M. Rosenfeld, Reconstructing Words Using Queries on Subwords or Factors, 40th International Symposium on Theoretical Aspects of Computer (STACS) 2023 (7-9 mars 2023, Hamburg, Germany) (doi, arxiv, hal).
G. Richomme, P. Séébold, A Characterization of Binary Morphisms Generating Lyndon Infinite Words, Proceedings of the 13th International Conference Words 2021, LNCS 12847, 160-171, 2021 (doi, arxiv, hal).
G. Richomme, exposé invité à Words 2019, Loughbourough 2019, United Kingdom. Titre final = A question around S-adicity, desubstitutions and property preserving morphisms.
G. Richomme, A Characterization of Infinite LSP Words, proceedings of the 21st International Conference on Developments in Language Theory (DLT 2017), Liège, Belgium, LNCS 10396, 320-331, 2017 (preprint on arxiv, 2017).
G. Gamard, G. Richomme, Determining Sets of Quasiperiods of Infinite Words, proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), LIPICs, vol. 58, article 40, 13 pages, 2016.
G. Gamard, G. Richomme, Coverability in Two Dimensions, proceedings of the 9th International Conference on Language and Automata, Theory and Applications (LATA 2015), Nice, France, LNCS 8977, 402-413, 2015.
M. Bucci, G. Richomme, Left greedy palindromic length, 15e Journées Montoises d'Informatique Théorique, Nancy, septembre 2014, actes en ligne.
F. Levé, G. Richomme, On Quasiperiodic Morphisms, Lecture Notes in Computer Science Volume 8079, Proceedings of Words 2013 (16-20 septembre 2013), pp 181-192, 2013 (voir aussi hal, arxiv).
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 (arxiv : Towards a statement of the S-adic conjecture through examples).
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 ).