14 citations · 54 across the 28 of their papers we have counts for
16 papers · 1 filter
Revisiting regular sequences in light of rational base numeration systems
Michel Rigo, Manon Stipulanti
Regular sequences generalize the extensively studied automatic sequences. Let be an abstract numeration system. When the numeration language is prefix-closed and regular, a…
Automatic sequences: from rational bases to trees
Michel Rigo, Manon Stipulanti
The th term of an automatic sequence is the output of a deterministic finite automaton fed with the representation of in a suitable numeration system. In this paper, instead…
On the binomial equivalence classes of finite words
Marie Lejeune, Michel Rigo, Matthieu Rosenfeld
Two finite words and are -binomially equivalent if, for each word of length at most , appears the same number of times as a subsequence (i.e., as a scattered…
Reconstructing Words from Right-Bounded-Block Words
Pamela Fleischmann, Marie Lejeune, Florin Manea +2
A reconstruction problem of words from scattered factors asks for the minimal information, like multisets of scattered factors of a given length or the number of occurrences of sca…
Taking-and-merging games as rewrite games
Eric Duchêne, Victor Marsault, Aline Parreau +1
This work is a contribution to the study of rewrite games. Positions are finite words, and the possible moves are defined by a finite number of local rewriting rules. We introduce…
Automatic sequences based on Parry or Bertrand numeration systems
Adeline Massuir, Jarkko Peltomäki, Michel Rigo
We study the factor complexity and closure properties of automatic sequences based on Parry or Bertrand numeration systems. These automatic sequences can be viewed as generalizatio…
An efficient algorithm to decide periodicity of b-recognisable sets using MSDF convention
Bernard Boigelot, Isabelle Mainz, Victor Marsault +1
Given an integer base , a set of integers is represented in base by a language over . The set is said to be -recognisable if its representation is a re…
Relations on words
Michel Rigo
In the first part of this survey, we present classical notions arising in combinatorics on words: growth function of a language, complexity function of an infinite word, pattern av…
A new approach to the -regularity of the -abelian complexity of -automatic sequences
Aline Parreau, Michel Rigo, Eric Rowland +1
We prove that a sequence satisfying a certain symmetry property is -regular in the sense of Allouche and Shallit, i.e., the -module generated by its -kernel is fi…
Avoiding 2-binomial squares and cubes
M. Rao, M. Rigo, P. Salimov
Two finite words are 2-binomially equivalent if, for all words of length at most 2, the number of occurrences of as a (scattered) subword of is equal to the numbe…
Numeration Systems: a Link between Number Theory and Formal Language Theory
Michel Rigo
We survey facts mostly emerging from the seminal results of Alan Cobham obtained in the late sixties and early seventies. We do not attempt to be exhaustive but try instead to give…
State Complexity of Testing Divisibility
Emilie Charlier, Narad Rampersad, Michel Rigo +1
Under some mild assumptions, we study the state complexity of the trim minimal automaton accepting the greedy representations of the multiples of m >= 2 for a wide class of linear…
Proceedings Twelfth Annual Workshop on Descriptional Complexity of Formal Systems
Ian McQuillan, Giovanni Pighizzini
The 12th annual workshop, Descriptional Complexity of Formal Systems 2010, is taking place in Saskatoon, Canada, on August 8-10, 2010. It is jointly organized by the IFIP Working G…
A note on syndeticity, recognizable sets and Cobham's theorem
M. Rigo, L. Waxweiler
In this note, we give an alternative proof of the following result. Let p, q >= 2 be two multiplicatively independent integers. If an infinite set of integers is both p- and q-reco…
A Decision Problem for Ultimately Periodic Sets in Non-standard Numeration Systems
J. Bell, E. Charlier, A. S. Fraenkel +1
Consider a non-standard numeration system like the one built over the Fibonacci sequence where nonnegative integers are represented by words over without two consecutive…
Multidimensional Generalized Automatic Sequences and Shape-symmetric Morphic Words
Emilie Charlier, Tomi Karki, Michel Rigo
An infinite word is S-automatic if, for all n>=0, its (n + 1)st letter is the output of a deterministic automaton fed with the representation of n in the considered numeration syst…