Back to search

University of Waterloo

State Complexity of Linear Relations and Linear Subsequences of Automatic Sequences

Abstract

dc:description.abstract

In 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

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Moradi, Delaram. State Complexity of Linear Relations and Linear Subsequences of Automatic Sequences. University of Waterloo, 2026. https://hdl.handle.net/10012/23044