11 papers
An example of an automatic sequence with non-regular abelian complexity
Jean-Paul Allouche, Narad Rampersad, Michel Rigo +2
Answering a question of Madill and Rampersad, we give an example a of a -automatic sequence whose abelian complexity is not -regular.
The speed of convergence in the Cooper-Dutle dueling game
Jeffrey Shallit
In 2013 Cooper and Dutle invented a dueling scenario where Alice and Bob shoot at each other until one is hit. Each shot is successful with some fixed probability , .…
Effective Computation of Generalized Abelian Complexity for Pisot Type Substitutive Sequences
Jean-Michel Couvreur, Martin Delacourt, Nicolas Ollinger +3
Generalized abelian equivalence compares words by their factors up to a certain bounded length. The associated complexity function counts the equivalence classes for factors of a g…
Additive word complexity and Walnut
Pierre Popoli, Jeffrey Shallit, Manon Stipulanti
In combinatorics on words, a classical topic of study is the number of specific patterns appearing in infinite sequences. For instance, many works have been dedicated to studying t…
The Repetition Threshold for Rote Sequences
Nicolas Ollinger, Jeffrey Shallit
We consider Rote words, which are infinite binary words with factor complexity . We prove that the repetition threshold for this class is . Our technique is purely computa…
The reflection complexity of sequences over finite alphabets
Jean-Paul Allouche, John M. Campbell, Shuo Li +2
In combinatorics on words, the well-studied factor complexity function $ρ_{\infw{x}}$ of a sequence $\infw{x}$ over a finite alphabet counts, for every nonnegative integer , the…
Using finite automata to compute the base- representation of the golden ratio and other quadratic irrationals
Aaron Barnoff, Curtis Bright, Jeffrey Shallit
We show that the 'th digit of the base- representation of the golden ratio is a finite-state function of the Zeckendorf representation of , and hence can be computed by…
Beatty Sequences for a Quadratic Irrational: Decidability and Applications
Luke Schaeffer, Jeffrey Shallit, Stefan Zorcic
Let and belong to the same quadratic field. We show that the inhomogeneous Beatty sequence is synchronized, in the sense that there is…
Repetition factorization of automatic sequences
Jeffrey Shallit, Xinhao Xu
Following Inoue et al., we define a word to be a repetition if it is a (fractional) power of exponent at least 2. A word has a repetition factorization if it is the product of repe…
Proof of Irvine's Conjecture via Mechanized Guessing
Jeffrey Shallit
We prove a recent conjecture of Sean A. Irvine about a nonlinear recurrence, using mechanized guessing and verification. The theorem-prover Walnut plays a large role in the proof.
Power-free Complementary Binary Morphisms
Jeffrey Shallit, Arseny M. Shur, Stefan Zorcic
We revisit the topic of power-free morphisms, focusing on the properties of the class of complementary morphisms. Such morphisms are defined over a -letter alphabet, and map the…