Automata and orders: the Wheeler class. Complexity, bounds, and operations

In this thesis we discuss Wheeler automata, a subclass of finite states automata (NFAs) ordered by co-lexicographic order on strings, which allows efficient storage and substring query mechanisms. Wheeler automata form an important data structure for languages, as the determinization process via powerset construction is polynomial, making classical problems solvable in polynomial time. We investigate computational problems related to recognizing Wheeler automata starting from NFAs and reduced NFAs, noting that non-determinism generally leads to intractability. We also examine state complexity in Wheeler DFAs and prove that intersection of languages is computationally simpler, and we provide a construction for the minimum Wheeler DFA. Additionally, we explore the Krohn-Rhodes Decomposition Theorem (KRDT) for two compression-oriented classes of automata: path-coherent and Wheeler automata. These classes are efficiently encodable and indexable. We prove that automata in these classes can be decomposed into a cascade with a number of components linear to the original automaton's states. For Wheeler automata, only two-state resets are needed, avoiding full KRDT through a simpler inductive argument. Lastly, we extend the analysis of Wheeler automata to arbitrary NFAs using a parameter called width, which indicates how far an automaton is from being Wheeler. Specifically, we focus on the difference between the width calculated on DFAs and that calculated on NFAs recognizing a given language, showing that their distance can be exponentially large and providing useful lower bounds for the latter.