The DOI matches its Crossref record; 27 of the 28 references it cites were found in a registry or an index; none of the 11 sources its claims cite is checked for support yet.
Decision algorithms for Fibonacci-automatic words, II: Related sequences and avoidability
Open accessOverview
CoChat Summary
TL;DR
The paper applies a Walnut-based decision procedure for Fibonacci-automatic words to related sequences, proving that the Rote-Fibonacci word is aperiodic and avoids the pattern \(xxx^R\), the first avoidability result for a nonuniform morphism proved purely mechanically. It also derives properties of the Rote-Fibonacci and Fibonacci-Thue-Morse words and identifies the lexicographically least \(S(b)\)-form sequence avoiding additive squares.
Key findings
- The Rote-Fibonacci word \(r\) is not ultimately periodic and avoids \(xxx^R\); the periodicity predicate returns false, and the \(xxx^R\) predicate accepts only \(n=0\) (Theorem 3).
- For \(r\): all squares have order \(F_{3n+1}\) for \(n\ge 0\); all cubes have order \(F_{3n+1}\) for \(n\ge 1\); palindromes occur at all lengths \(\ge 0\); antipalindromes occur at all orders \(\ge 0\); antisquares have orders \(F_{3n+2}\) and \(F_{3n+3}\) for \(n\ge 0\). Its critical exponent is \(2+\alpha\), its subword complexity is \(2n\), it is mirror invariant, and it avoids \(xx^R x^R\) (Theorem 4, Corollary 6, Theorem 7, Theorem 8, Corollary 9).
- For periodic avoidance: for \(k\ge 1\), with \(n=2F_{3k+2}\) and \(z=r[0..n-1]\), the periodic word \(z^\omega\) contains no occurrence of \(xxx^R\) (Theorem 12). For the Fibonacci-Thue-Morse word \(v\): only squares are of order \(4\) and \(F_n\) for \(n\ge 2\); only cubes are \(000\) and \(111\); only overlaps are of order \(F_{2n}\) for \(n\ge 1\); there are no superoverlaps; there are only 31 distinct palindromes including the empty string, the longest of length 12; \(v\) is recurrent; and the first difference sequence of its subword complexity is Fibonacci-automatic, generated by a 46-state automaton (Theorem 15, Theorem 16, Theorem 17).
- The lexicographically least sequence over \(\mathbb N^*\) of the form \(S(b)\) that avoids additive squares is \(a=1213121512131218\cdots\), where \(b[i]:=F_{i+2}\) (Theorem 18).
Methods
- The main technique is the decision procedure from the previous paper: assertions about Fibonacci-automatic sequences are written in the first-order theory of the natural numbers with addition and indexing into the sequences, then translated into automata accepting the Fibonacci representations of the free variables that make the predicate true.
- The implementation is Walnut; the paper provides Walnut commands for many examples. It applies the method to the Rote-Fibonacci word \(r\), the Fibonacci-Thue-Morse sequence \(v\), and an additive-square avoidability problem.
- For additive squares, a modified decision procedure is used with auxiliary DFAs handling unnormalized Fibonacci representations and base-2 arithmetic, including automata such as a 6-state \(M_{\text{add22F}}\) and a 5-state \(M_{\text{1uFisZero}}\). The authors report running Walnut with `java -Xmx11000M -d64 Main.prover`.
Limitations
- The paper states unresolved conjectures and open problems: Conjecture 10 (every infinite binary word avoiding \(xxx^R\) has critical exponent \(\ge 2+\alpha\)), Conjecture 11 on primitive \(z\), Open Problem 13 on counting binary words avoiding both \(xxx^R\) and \((2+\alpha)\)-powers, and Conjecture 14 on minimal \(x\).
- The paper states computational resource limits: for recurrence, an intermediate NFA of 1159 states could not be determinized within available space, requiring a rewritten predicate; for Theorem 12 cases, the predicates required more space than available, so the computation was restricted to \(n\) whose Fibonacci representation is of the form \(10010^*\) to terminate.
- Evident from the text: several results depend on the correctness of the Walnut/decision-procedure implementation, and some details are omitted (e.g., for Theorem 17 the authors “omit the details” of constructing the automaton for \(d(n)\)), though Walnut commands are provided for independent verification.
Model-written summary. Check it against the paper before relying on it.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
0 Valid · 1 Not valid · 7 Not checked · 57 Own results and interpretations
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“The Rote-Fibonacci word is mirror invariant.That is, if z is a factor of r then so is z R .”
§ Decision algorithms for Fibonacci-automatic words, II: Related sequences and avoidability > Theorem 7. The Rote-Fibonacci word has subword complexity 2n.
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“All squares in the Rote-Fibonacci word are of order F 3n+1 for n ≥ 0, and each such order occurs.”
§ Decision algorithms for Fibonacci-automatic words, II: Related sequences and avoidability > Theorem 4.
plainstates an association- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Theorem 17.The first difference sequence (d(n)) n≥0 of the subword complexity of v is Fibonacci-automatic, and is generated by the following automaton.”
§ Decision algorithms for Fibonacci-automatic words, II: Related sequences and avoidability > Theorem 16. The word v is recurrent.
plainstates an association- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
A result the paper states — it cites no source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Then for all m, m ≥ 0 we have |A(m , n, j) -A(m, n, j)| ≤ 1.”
§ Decision algorithms for Fibonacci-automatic words, II: Related sequences and avoidability > 6. Combining two representations and avoidability
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“(c) The only overlaps in v are of order F 2n for n ≥ 1, and an overlap of each such order occurs.”
§ Decision algorithms for Fibonacci-automatic words, II: Related sequences and avoidability > Theorem 15.
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
46 more claims
Create a free account to see all 65 claims and every source verdict.
- It may state two separate claims as one. 7
- Probably not a substantial claim. 9
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
Each contradiction between two passages listed here was confirmed by an independent check.
Rated minor: it would not touch a result — a value no result rests on, a p-value that stays on the same side of the significance level, or a conflict that is clerical, resolved elsewhere in the paper, or outside its own findings.
In the paper
§ Decision algorithms for Fibonacci-automatic words, II: Related sequences and avoidability > Theorem 7. The Rote-Fibonacci word has subword complexity 2n.
“Then by Theorem 8 we know that (xx R x R ) R = xxx R occurs in f.”
§ Decision algorithms for Fibonacci-automatic words, II: Related sequences and avoidability > Theorem 7. The Rote-Fibonacci word has subword complexity 2n.
“The Rote-Fibonacci word is mirror invariant.That is, if z is a factor of r then so is z R .”
Rated minor: it would not touch a result — a value no result rests on, a p-value that stays on the same side of the significance level, or a conflict that is clerical, resolved elsewhere in the paper, or outside its own findings.
In the paper
§ Decision algorithms for Fibonacci-automatic words, II: Related sequences and avoidability > 6. Combining two representations and avoidability
“i+n-1 k=i a[k] = log 2 (i+n) j=0 A(i, n, j)F j+2”
§ Decision algorithms for Fibonacci-automatic words, II: Related sequences and avoidability > 6. Combining two representations and avoidability
“Let A(m, n, j) denote the number of occurrences of j in ν 2 (m + 1), . . ., ν 2 (m + n).”
Rated minor: it would not touch a result — a value no result rests on, a p-value that stays on the same side of the significance level, or a conflict that is clerical, resolved elsewhere in the paper, or outside its own findings.
In the paper
§ Decision algorithms for Fibonacci-automatic words, II: Related sequences and avoidability > Theorem 15.
“∀i ∃ j > i ∀k ≥ 1 ∀u, i ≤ u < n + i (i = j + k) =⇒ v[u] = v[u + k],”
§ Decision algorithms for Fibonacci-automatic words, II: Related sequences and avoidability > Theorem 15.
“∀i ∃ j > i (∀t ((t < n) =⇒ (v[i + t] = v[ j + t]))).”
Rated minor: it would not touch a result — a value no result rests on, a p-value that stays on the same side of the significance level, or a conflict that is clerical, resolved elsewhere in the paper, or outside its own findings.
In the paper
§ Decision algorithms for Fibonacci-automatic words, II: Related sequences and avoidability > 6. Combining two representations and avoidability
“using only the first occurrence of the change at a[2 s -1]”
§ Decision algorithms for Fibonacci-automatic words, II: Related sequences and avoidability > 6. Combining two representations and avoidability
“a[i] = b[ν 2 (i)]”
Citations
Cites
Fraenkel, A. S. (1985) · American Mathematical Monthly · doi:10.1080/00029890.1985.11971550 · Cited by 223
Bemerkungen zur Theorie der Diophantischen Approximationen
Ostrowski, A. M. (1922) · Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg · doi:10.1007/bf02940581 · Cited by 206
Automatic Theorem Proving in WalnutPreprint
Mousavi, H. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1603.06017 · Cited by 158
Self-citationSequences With Subword Complexity 2n
Rote, G. (1994) · Journal of Number Theory · doi:10.1006/jnth.1994.1012 · Cited by 95
Voorstelling van natuurlijke getallen door een som van getallen van fibonacci
Lekkerkerker, C. G. (1951) · Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands · Cited by 64
A generalization of automatic sequences
Shallit, J. O. (1988) · Theoretical Computer Science · doi:10.1016/0304-3975(88)90103-x · Cited by 58
Self-citationCarlitz, L. (1968) · The Fibonacci Quarterly · doi:10.1080/00150517.1968.12431213 · Cited by 50
Decision algorithms for Fibonacci-automatic Words, I: Basic results
Mousavi, H., Schaeffer, L., & Shallit, J. O. (2016) · RAIRO - Theoretical Informatics and Applications · doi:10.1051/ita/2016010 · Cited by 45
Self-citationArithmetic progressions in lacunary sets
Brown, T. C., & Freedman, A. R. (1987) · Rocky Mountain Journal of Mathematics · doi:10.1216/rmj-1987-17-3-587 · Cited by 39
Avoiding Three Consecutive Blocks of the Same Size and Same Sum
Cassaigne, J., Currie, J. D., Schaeffer, L., & Shallit, J. O. (2014) · Journal of the ACM · doi:10.1145/2590775 · Cited by 36
Self-citation
Research works printed but not linked: 2
- Blondin Massé, 2011, Fibonacci snowflakes, Ann. Sci. Math. Québec, 35, 141
- Zeckendorf, 1972, Représentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas, Bull. Soc. Roy. Sci. Liège, 41, 179
Cited by
Automatic Theorem Proving in WalnutPreprint
Mousavi, H. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1603.06017 · Cited by 158
Self-citationDecision algorithms for Fibonacci-automatic Words, I: Basic results
Mousavi, H., Schaeffer, L., & Shallit, J. O. (2016) · RAIRO - Theoretical Informatics and Applications · doi:10.1051/ita/2016010 · Cited by 45
Self-citationDecision Algorithms for Fibonacci-Automatic Words, III: Enumeration and Abelian Properties
Du, C. F., Mousavi, H., Schaeffer, L., & Shallit, J. O. (2016) · International Journal of Foundations of Computer Science · doi:10.1142/s0129054116500386 · Cited by 23
Self-citationAdditive Number Theory via Automata Theory
Rajasekaran, A., Shallit, J. O., & Smith, T. (2019) · Theory of Computing Systems · doi:10.1007/s00224-019-09929-9 · Cited by 19
Self-citationSums of Palindromes: an Approach via AutomataPreprint
Rajasekaran, A., Shallit, J. O., & Smith, T. (2017) · arXiv (Cornell University) · doi:10.4230/lipics.stacs.2018.54 · Cited by 12
Self-citationBeatty sequences for a quadratic irrational: Decidability and applications
Schaeffer, L., Shallit, J. O., & Zorcic, S. (2026) · Discrete Mathematics · doi:10.1016/j.disc.2026.115183 · Cited by 10
Self-citationSumsets of Wythoff sequences, Fibonacci representation, and beyond
Shallit, J. O. (2021) · Periodica Mathematica Hungarica · doi:10.1007/s10998-021-00390-1 · Cited by 8
Self-citationA Lebesgue Integral Variant of the Additive Square Problem
Vukusic, I. (2025) · American Mathematical Monthly · doi:10.1080/00029890.2025.2545706 · Cited by 2
Rampersad, N. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-58741-7_10 · Cited by 1
The Hurt-Sada Array and Zeckendorf Representations
Shallit, J. O. (2026) · The Fibonacci Quarterly · doi:10.1080/00150517.2025.2551839 · Cited by 1
Self-citationSums of Palindromes: an Approach via Nested-Word Automata.Preprint
Rajasekaran, A., Shallit, J. O., & Smith, T. (2017) · arXiv (Cornell University)
Self-citationOn Modelling the Avoidability of Patterns as CSPPreprint
Ehlers, T., Manea, F., Nowotka, D., & Reshadi, K. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1906.00715
Zeckendorf expansion, Dirichlet series and infinite series involving the infinite Fibonacci wordPreprint
Li, S. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2106.05672
Decidability of extensions of Presburger arithmetic by generalised polynomials
Konieczny, J. (2025) · Logical Methods in Computer Science · doi:10.46298/lmcs-21(4:1)2025
Évitabilité de puissances additives en combinatoire des mots
Liétard, F. (2020) · theses.fr (ABES) · doi:10.70675/71ac03bdz338fz4b4bz8f14z395588374235
Metadata
- Authors
- Du, C. F., Mousavi, H., Rowland, E., Schaeffer, L., & Shallit, J.
- Affiliations
- University of Waterloo (CA)
- Hofstra University (US)
- MIT Computer Science and Artificial Intelligence Laboratory (US)
- Corresponding author
- Shallit, Jeffrey
- Venue
- Theoretical Computer Science
- Publisher
- Elsevier BV
- Published
- 2017-01
- Volume
- 657
- Pages
- 146-162
- ISSN
- 0304-3975 (ISSN-L)
- OpenAlex
- W2538425405
- Semantic Scholar
- b5b6d01beef5fa4058b6a565b26173298f2f413f
- Cited by
- 16
- References
- 28
- Citations by year
- 2026: 2 · 2025: 2 · 2021: 2 · 2020: 1 · 2019: 3 · 2017: 3
- FWCI
- 2.48
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Licence
- www.elsevier.com/tdm/userlicense/1.0/ (tdm)
- www.elsevier.com/open-access/userlicense/1.0/ (vor, 1462 d)
- Locations
- Theoretical Computer Science (publishedVersion)
- Funders
- NSERC (RGPIN-105829-2013)
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › semigroups and automata theory
- Physical Sciences › Mathematics › Theoretical Computer Science › Algorithms and Data Compression
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Computability, Logic, AI Algorithms
- Keywords
- decision-making algorithm, avoidability, pattern avoidance, automatic sequences
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
A language model drew the claims from the paper on 2026-11-17, under version 3 of the claim definition (model deepseek-v4.1-flash, prompt extract-v3).
A second model labelled each claim on 2026-11-17 (model jev-1.13-20260917, definition revision gold-guideline-v0.2).
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.