Back to search

The Open University

Automatic sequences from algebraic, dynamical, and computational perspectives

Abstract

dc:description.abstract

We 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

Chain of custody

source
Harvested from
The Open University
Base URL
oro.open.ac.uk/cgi/oai2
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Joshi, Gandhar. Automatic sequences from algebraic, dynamical, and computational perspectives. doctoral thesis, The Open University, 2025.