Michel Rigo
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Michel Rigo has a total of 79 co-authors. Here are the top co-authors by number of shared publications:
- Manon Stipulanti
Department of Mathematics University of Liège Belgium
9 shared publications - Markus A. Whiteland
Department of Computer Science, Loughborough University, Loughborough, UK
9 shared publications - Émilie Charlier
Department of Mathematics ULiège Liège Belgium
8 shared publications - Valérie Berthé
Université Paris Cité, CNRS, IRIF, Paris, France
5 shared publications - Antoine Renard
Department of Mathematics, University of Liège, Liège, Belgium
4 shared publications - Marie Lejeune
University of Liège
4 shared publications
Latest Publications
- 6 June 2026
- Published by Springer Nature
- p. 43-56
Thue–Morse Series and k-ary Partitions
- 23 February 2026
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 385, 280-296
A word reconstruction problem for polynomial regular languages
- 23 February 2026
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 385, 280-296
A word reconstruction problem for polynomial regular languages
- 15 December 2025
- Published by Elsevier in Journal of Combinatorial Theory, Series A
- Vol. 220
Computing the k-binomial complexity of generalized Thue–Morse words
- 15 December 2025
- Published by Elsevier in Journal of Combinatorial Theory, Series A
- Vol. 220
Computing the k-binomial complexity of generalized Thue–Morse words
- Open Access
Variants of Wythoff game with terminal positions or blocking maneuvers
We show how the software Walnut can be used to obtain concise proofs of results concerning variants of the famous Wythoff game, in which blocking maneuvers or terminal positions are added, as discussed respectively by Larsson (2011) and Komak et al. (2025). Our approach provides automatic proofs that both confirm and extend their results, and the same techniques apply to newly introduced variants as well. Then, using classic techniques, we obtain new recursive and morphic characterizations of Wythoff-type games where the set of terminal positions $(x,y)$ satisfy $x+y\le\ell$. The use of Walnut in combinatorial game theory is relatively recent, and only a few examples have been explored so far. The Wythoff game, being directly connected to the Fibonacci numeration system, proves especially well-suited to this kind of approach. It permits us to solve instances for a fixed value of a parameter.Open AccessVariants of Wythoff game with terminal positions or blocking maneuvers
We show how the software Walnut can be used to obtain concise proofs of results concerning variants of the famous Wythoff game, in which blocking maneuvers or terminal positions are added, as discussed respectively by Larsson (2011) and Komak et al. (2025). Our approach provides automatic proofs that both confirm and extend their results, and the same techniques apply to newly introduced variants as well. Then, using classic techniques, we obtain new recursive and morphic characterizations of Wythoff-type games where the set of terminal positions $(x,y)$ satisfy $x+y\le\ell$. The use of Walnut in combinatorial game theory is relatively recent, and only a few examples have been explored so far. The Wythoff game, being directly connected to the Fibonacci numeration system, proves especially well-suited to this kind of approach. It permits us to solve instances for a fixed value of a parameter. - 18 September 2025
- Published by Springer Nature in International Journal of Game Theory
- Vol. 54 (2) , 1-32
Automatic proofs in combinatorial game theory
- 18 September 2025
- Published by Springer Nature in International Journal of Game Theory
- Vol. 54 (2) , 1-32
Automatic proofs in combinatorial game theory
- Open Access
Computing Expansions in Infinitely Many Cantor Real Bases via a Single Transducer
Representing real numbers using convenient numeration systems (integer bases, $β$-numeration, Cantor bases, etc.) has been a longstanding mathematical challenge. This paper focuses on Cantor real bases and, specifically, on automatic Cantor real bases and the properties of expansions of real numbers in this setting. We develop a new approach where a single transducer associated with a fixed real number $r$, computes the $\mathbf{B}$-expansion of $r$ but for an infinite family of Cantor real bases $\mathbf{B}$ given as input. This point of view contrasts with traditional computational models for which the numeration system is fixed. Under some assumptions on the finitely many Pisot numbers occurring in the Cantor real base, we show that only a finite part of the transducer is visited. We obtain fundamental results on the structure of this transducer and on decidability problems about these expansions, proving that for certain classes of Cantor real bases, key combinatorial properties such as greediness of the expansion or periodicity can be decided algorithmically.Open AccessComputing Expansions in Infinitely Many Cantor Real Bases via a Single Transducer
Representing real numbers using convenient numeration systems (integer bases, $β$-numeration, Cantor bases, etc.) has been a longstanding mathematical challenge. This paper focuses on Cantor real bases and, specifically, on automatic Cantor real bases and the properties of expansions of real numbers in this setting. We develop a new approach where a single transducer associated with a fixed real number $r$, computes the $\mathbf{B}$-expansion of $r$ but for an infinite family of Cantor real bases $\mathbf{B}$ given as input. This point of view contrasts with traditional computational models for which the numeration system is fixed. Under some assumptions on the finitely many Pisot numbers occurring in the Cantor real base, we show that only a finite part of the transducer is visited. We obtain fundamental results on the structure of this transducer and on decidability problems about these expansions, proving that for certain classes of Cantor real bases, key combinatorial properties such as greediness of the expansion or periodicity can be decided algorithmically. - 1 March 2025
- Published by Springer Nature in Journal of Algebraic Combinatorics
- Vol. 61 (2) , 1-33
Introducing q-deformed binomial coefficients of words
- 1 March 2025
- Published by Springer Nature in Journal of Algebraic Combinatorics
- Vol. 61 (2) , 1-33
Introducing q-deformed binomial coefficients of words
- Open Access
Computing the k-binomial complexity of generalized Thue--Morse words
Two finite words are k-binomially equivalent if each subword (i.e., subsequence) of length at most k occurs the same number of times in both words. The k-binomial complexity of an infinite word is a function that maps the integer $n\geq 0$ to the number of k-binomial equivalence classes represented by its factors of length n. The Thue--Morse (TM) word and its generalization to larger alphabets are ubiquitous in mathematics due to their rich combinatorial properties. This work addresses the k-binomial complexities of generalized TM words. Prior research by Lejeune, Leroy, and Rigo determined the k-binomial complexities of the 2-letter TM word. For larger alphabets, work by Lü, Chen, Wen, and Wu determined the 2-binomial complexity for m-letter TM words, for arbitrary m, but the exact behavior for $k\geq 3$ remained unresolved. They conjectured that the k-binomial complexity function of the m-letter TM word is eventually periodic with period $m^k$. We resolve the conjecture positively by deriving explicit formulae for the k-binomial complexity functions for any generalized TM word. We do this by characterizing k-binomial equivalence among factors of generalized TM words. This comprehensive analysis not only solves the open conjecture, but also develops tools such as abelian Rauzy graphs.Open AccessComputing the k-binomial complexity of generalized Thue--Morse words
Two finite words are k-binomially equivalent if each subword (i.e., subsequence) of length at most k occurs the same number of times in both words. The k-binomial complexity of an infinite word is a function that maps the integer $n\geq 0$ to the number of k-binomial equivalence classes represented by its factors of length n. The Thue--Morse (TM) word and its generalization to larger alphabets are ubiquitous in mathematics due to their rich combinatorial properties. This work addresses the k-binomial complexities of generalized TM words. Prior research by Lejeune, Leroy, and Rigo determined the k-binomial complexities of the 2-letter TM word. For larger alphabets, work by Lü, Chen, Wen, and Wu determined the 2-binomial complexity for m-letter TM words, for arbitrary m, but the exact behavior for $k\geq 3$ remained unresolved. They conjectured that the k-binomial complexity function of the m-letter TM word is eventually periodic with period $m^k$. We resolve the conjecture positively by deriving explicit formulae for the k-binomial complexity functions for any generalized TM word. We do this by characterizing k-binomial equivalence among factors of generalized TM words. This comprehensive analysis not only solves the open conjecture, but also develops tools such as abelian Rauzy graphs. - Open Access
- 10 October 2024
- Published by Springer Nature in Theory of Computing Systems
- Vol. 68 (6) , 1622-1639
Automatic Abelian Complexities of Parikh-Collinear Fixed Points
Parikh-collinear morphisms have the property that all the Parikh vectors of the images of letters are collinear, i.e., the associated adjacency matrix has rank 1. In the conference DLT–WORDS 2023 we showed that fixed points of Parikh-collinear morphisms are automatic. We also showed that the abelian complexity function of a binary fixed point of such a morphism is automatic under some assumptions. In this note, we fully generalize the latter result. Namely, we show that the abelian complexity function of a fixed point of an arbitrary, possibly erasing, Parikh-collinear morphism is automatic. Furthermore, a deterministic finite automaton with output generating this abelian complexity function is provided by an effective procedure. To that end, we discuss the constant of recognizability of a morphism and the related cutting set.
- 10 October 2024
- Published by Springer Nature in Theory of Computing Systems
- Vol. 68 (6) , 1622-1639
Open AccessAutomatic Abelian Complexities of Parikh-Collinear Fixed Points
Parikh-collinear morphisms have the property that all the Parikh vectors of the images of letters are collinear, i.e., the associated adjacency matrix has rank 1. In the conference DLT–WORDS 2023 we showed that fixed points of Parikh-collinear morphisms are automatic. We also showed that the abelian complexity function of a binary fixed point of such a morphism is automatic under some assumptions. In this note, we fully generalize the latter result. Namely, we show that the abelian complexity function of a fixed point of an arbitrary, possibly erasing, Parikh-collinear morphism is automatic. Furthermore, a deterministic finite automaton with output generating this abelian complexity function is provided by an effective procedure. To that end, we discuss the constant of recognizability of a morphism and the related cutting set.