Subword complexity of the Fibonacci-Thue-Morse sequence: the proof of Dekking's conjecture

DOI10.1016/J.INDAG.2021.03.004MaRDI QIDQ2020439zbMATH OpenOpenAlexWikidataFDO

Authors Jeffrey Shallit

Publication date 23 April 2021

Published in Indagationes Mathematicae. New Series (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2010.10956

zbMATH Keywords

decision procedurefinite automatonFibonacci representationsubword complexityFibonacci-Thue-Morse sequence

Mathematics Subject Classification ID

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

Abstract: Recently Dekking conjectured the form of the subword complexity function for the Fibonacci-Thue-Morse sequence. In this note we prove his conjecture by purely computational means, using the free software Walnut.

Recommendations

• Note on a Fibonacci parity sequence
• scientific article; zbMATH DE number 7069796
• The subword complexity of polynomial subsequences of the Thue-Morse sequence
• On minimal words with given subword complexity
• Decision algorithms for Fibonacci-automatic words. I: Basic results.

Cites work

• scientific article; zbMATH DE number 3664335 (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?)
• An analogue of the Thue-Morse sequence
• Automatic Sequences
• Decision algorithms for Fibonacci-automatic words. I: Basic results.
• Decision algorithms for Fibonacci-automatic words. III: Enumeration and abelian properties.
• Enumeration of factors in the Thue-Morse word
• Ostrowski-automatic sequences: theory and applications
• Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups
• The sum of digits functions of the Zeckendorf and the base phi expansions

Cited in

(7)

• On a conjecture of J. Shallit
• On the structure of compacted subword graphs of Thue-Morse words and their applications
• Maximum order complexity of the sum of digits function in Zeckendorf base and polynomial subsequences
• Note on a Fibonacci parity sequence
• Some tribonacci conjectures
• Complexity and special factors
• Proof of a conjecture of Krawchuk and Rampersad on the cyclic complexity of the Thue-Morse sequence

Describes a project that uses

Uses Software

• Walnut

This page was built for publication: Subword complexity of the Fibonacci-Thue-Morse sequence: the proof of Dekking's conjecture

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