University of Waterloo
State Complexity of Linear Relations and Linear Subsequences of Automatic Sequences
Abstract
dc:description.abstractIn this thesis, we study the state complexity of specific formal languages; for example, we study the number of states required in the minimal automaton reading the representation of two integers $i, j$ in parallel and accepting them if and only $i+c = j$ for some constant integer $c \geq 1$. We also study the state complexity of linear subsequences of automatic sequences; for example, we study the number of states required in the minimal automaton generating the linear subsequence (h(i+c))i \geq 0 for some automatic sequences (h(i))i \geq 0 and some constant integer $c \geq 1$. Moreover, we study the runtime complexity of generating automata for specific formal languages and linear subsequences of automatic sequences using a reasonable interpretation of B\"uchi arithmetic; for example we study the runtime complexity of creating an automaton reading the representation of two integers $i, j$ in parallel and accepting them if and only if $ni=j$ for some constant $n \geq 2$. We also state some open problems. The above topics are studied both for automata with input in base-$k$ representation for some integer $k \geq 2$ and for automata with input in Fibonacci representation. Most results are for automata reading input in most-significant-digit-first format and some results are stated for automata reading input in least-significant-digit-first format.
Degree
thesis:*- Grantor dc:publisher
- University of Waterloo
- Year dc:date.issued
- 2026
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Moradi, Delaram
Rights
- Language dc:language.iso
- en
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- https://hdl.handle.net/10012/23044