The Open University
Automatic sequences from algebraic, dynamical, and computational perspectives
Abstract
dc:description.abstractWe investigate some interesting properties of automatic sequences and other relative families of sequences using three broadly distinguished approaches: algebraic, dynamical, and computational. We consider the semigroup associated to a primitive substitution. We use it to construct a minimal automaton which generates a bi-infinite substitution sequence <i>u</i> in reverse reading. We show, in the case where the substitution has a coincidence, that this automaton completely describes the semicocycle discontinuities of <i>u</i>. We investigate the lengths of the longest monochromatic arithmetic progressions for a fixed difference in Sturmian sequences. We provide a complete classification for their lengths using a simple set of formulae. Our strongest results are proved using methods from dynamical systems, especially the dynamics of circle rotations. We use the automatic theorem-proving software called walnut to study two combinatorial properties of automatic sequences: the monochromatic arithmetic progressions in Sturmian sequences that are automatic with respect to a regular numeration system, and the lengths, positions, and structure of the longest Hamiltonian words in the Thue–Morse sequence and the Fibonacci word.
Degree
thesis:*- Name dc:type.qualificationname
- phd
- Level dc:type.qualificationlevel
- doctoral
- Grantor dc:publisher.institution
- The Open University
- Year dc:date.issued
- 2025
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Joshi, Gandhar
Rights
- Language dc:language
- en