Limited Existential and Universal Width Alternating Finite Automata

Abstract

There have been many studies on several models of limited nondeterministic finite automata (NFAs), including studies on tree width, branching, guessing, and ambiguity of NFAs. However, the study of limited alternating finite automata (AFAs), a generalization of NFAs that allows for alternation between existential and universal states, is fairly new in the literature. Drawing inspiration from limited NFAs, recent studies have introduced maximal and optimal existential and universal widths of AFAs, designed to quantify the amount of existential and universal power used by an AFA. In this thesis, I explore the relation between limited optimal existential and universal width AFAs, limited maximal existential and universal width AFAs, NFAs, universal finite automata (UFAs), and deterministic finite automata (DFAs). More specifically, the study focuses on the state complexity of those models and the way they relate to each other. I show improved upper bounds for converting limited existential and/or universal width AFAs into NFAs, UFAs, and DFAs, largely using improved variations of subset construction. I also establish lower bounds for the size of NFAs, UFAs, and DFAs simulating limited existential and/or universal width AFAs. Although the upper and lower bounds provided are not the same, they are reasonably close.