Student or educator? Sign up with your school email and get 6 months of Pro free.

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 access
Du, Chen Fei, Mousavi, Hamoon, Rowland, Eric, Schaeffer, Luke, Shallit, Jeffrey · 2017 · Theoretical Computer Science

Overview

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

Crossref · 10.1016/j.tcs.2016.10.005

Cites

27 of 27 references verified0 citation errors · 0 not checkable

Statistics

Nothing to recompute.

Verification

Claims the paper makes

0 Valid · 1 Not valid · 7 Not checked · 57 Own results and interpretations

46 more claims

Create a free account to see all 65 claims and every source verdict.

See all claims — free account
  • It may state two separate claims as one. 7
  • Probably not a substantial claim. 9

Create a free account to see these claims.

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.

4 of 4

Citations

Cites

Show all 28 references

Research works printed but not linked: 2

  1. Blondin Massé, 2011, Fibonacci snowflakes, Ann. Sci. Math. Québec, 35, 141
  2. 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

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
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
Licence
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.