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

DOI10.1016/J.INDAG.2021.03.004zbMATH Open1489.11046arXiv2010.10956OpenAlexW3137198537WikidataQ113872391 ScholiaQ113872391MaRDI QIDQ2020439FDOQ2020439

Authors: Jeffrey Shallit 

Publication date: 23 April 2021

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

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.

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

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.

zbMATH Keywords

decision procedurefinite automatonFibonacci representationsubword complexityFibonacci-Thue-Morse sequence

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Automatic Sequences
• Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups
• Title not available (Why is that?)
• Title not available (Why is that?)
• Decision algorithms for Fibonacci-automatic words. I: Basic results.
• Enumeration of factors in the Thue-Morse word
• Decision algorithms for Fibonacci-automatic words. III: Enumeration and abelian properties.
• The sum of digits functions of the Zeckendorf and the base phi expansions
• Ostrowski-automatic sequences: theory and applications
• An analogue of the Thue-Morse sequence

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

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)