The additive complexity conjecture for automatic sequences
The additive complexity conjecture for automatic sequences
Let be an integer, and let be a -automatic sequence over a finite set of non-negative integers. Its additive complexity is the function assigning to each positive integer the number of distinct sums of length- factors of .
Additive complexity conjecture. The additive complexity of a -automatic sequence is a -regular sequence.
This conjecture extends the analogous conjecture for abelian complexity. The paper proves a particular case, while the general statement remains open.
Sources & referencesView supporting material
Primary source
Pierre Popoli, Jeffrey Shallit and Manon Stipulanti, “Additive word complexity and Walnut”, arXiv:2410.02409 (2024).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.