Limited Existential and Universal Width Alternating Finite Automata
Loading...
Authors
Zakzok, Mohammad
Date
2024-04-30
Type
thesis
Language
eng
Keyword
Automata Theory , State Complexity , Complexity Theory , Theoritical Computer Science
Alternative Title
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.
Description
Citation
Publisher
License
Queen's University's Thesis/Dissertation Non-Exclusive License for Deposit to QSpace and Library and Archives Canada
ProQuest PhD and Master's Theses International Dissemination Agreement
Intellectual Property Guidelines at Queen's University
Copying and Preserving Your Thesis
This publication is made available by the authority of the copyright owner solely for the purpose of private study and research and may not be copied or reproduced except as permitted by the copyright laws without written authority from the copyright owner.
Attribution-NonCommercial-NoDerivatives 4.0 International
ProQuest PhD and Master's Theses International Dissemination Agreement
Intellectual Property Guidelines at Queen's University
Copying and Preserving Your Thesis
This publication is made available by the authority of the copyright owner solely for the purpose of private study and research and may not be copied or reproduced except as permitted by the copyright laws without written authority from the copyright owner.
Attribution-NonCommercial-NoDerivatives 4.0 International