Repetition factorization of automatic sequences

DOI10.1142/S0129054124430019MaRDI QIDQ6989489zbMATH OpenFDO

Authors Narad Rampersad, Jeffrey Shallit, Xinhao Xu

Publication date 30 April 2025

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S0129054124430019

zbMATH Keywords

automatic sequenceFibonacci sequencepaperfolding sequenceperiodicityrepetitionrepetition factorizationRudi-Shapiro sequenceThue-Morse sequenceWalnut

Mathematics Subject Classification ID

Automata sequences (11B85) Combinatorics on words (68R15)

Review text

In combinatorics on words, a repetition is a (fractional) power of exponent at least \(2\) and a word has a repetition factorization if it is the product of repetitions. After the preliminaries in Section 1, Section 2 is devoted to the general case of repetition factorizations in (generalized) automatic sequences, where the famous theorem of Büchi, linking first-order logic to automatic sequences, is used. The subsequent sections are devoted to specific sequences where the results are made more precise using the theorem prover \texttt{Walnut}: Section 3 is devoted to the Fibonacci sequence, Section 4 to the Thue-Morse sequence, Section 5 to paperfolding sequences, and Section 6 to the Rudin-Shapiro sequence. The paper ends with Section 7 where the authors present some open problems for further investigation.

Cites work

• Automatic Sequences
• Factorizing strings into repetitions
• scientific article; zbMATH DE number 3947643 (Why is no real title available?)
• scientific article; zbMATH DE number 3229502 (Why is no real title available?)
• scientific article; zbMATH DE number 3397597 (Why is no real title available?)
• scientific article; zbMATH DE number 3076700 (Why is no real title available?)
• Largest repetition factorization of Fibonacci words
• Logic and p-recognizable sets of integers
• Some Theorems on Fourier Coefficients
• The first-order theory of binary overlap-free words is decidable
• The Logical Approach to Automatic Sequences
• The structure of the set of cube-free Z-words in a two-letter alphabet
• Uniformly growing k-th power-free homomorphisms
• Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen.

This page was built for publication: Repetition factorization of automatic sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6989489)