New metrics for finite automaton complexity and subregular language hierarchies
Loading...
Authors
Keeler, Casey
Date
Type
thesis
Language
eng
Keyword
Finite Automata , Ambiguity , Tree Width , Paths , String Path Width , Depth Path Width , Acyclic , Nearly Acyclic , Regular , Subregular , Languages
Alternative Title
Abstract
The degree of ambiguity of nondeterministic finite automata (NFA) has been studied significantly since at least the 1980s.
Roughly speaking, the degree of ambiguity counts the number of accepting computations of an NFA.
To get a more comprehensive understanding of the branching complexity of NFAs, we introduce and study the string path width and depth path width measures.
The string path width on a string w counts the number of all accepting and non-accepting computations on w, and the depth path width on an integer l counts the number of all accepting and non-accepting computations of a length l.
We focus on cases where these measures are finite, that is, there is some input which has maximal string or depth path width.
We give algorithms to decide the finiteness of the string and depth path width of an NFA.
The latter algorithm relies on structural properties that characterize NFAs with finite depth path width, and the former is based on existing algorithms to compute the degree of ambiguity.
We give upper bounds for the finite string and depth path width of an NFA or a DFA (deterministic finite automaton).
It is well known that acyclic NFAs define exactly the class of finite languages.
We consider less restrictive conditions that define the class of nearly acyclic NFAs.
An NFA is nearly acyclic if it does not have two cycles where one can be reached from the other.
It is shown that the nearly acyclic NFAs are exactly the NFAs with finite depth path width.
We study and introduce variants of existing subregular language families.
We establish (non)-inclusion relationships for these new classes, relative to each other and their existing counterparts.
Additionally we show that an infinite hierarchy exists within the most powerful new family, generalized word-definite languages.
We examine the structural limitations and give maximal examples of nearly acyclic NFAs.
We also show that nearly acyclic NFAs recognize the class of generalized word-definite languages.
For nearly acyclic DFAs, we establish a stronger correspondence: they recognize all generalized word-definite languages, and any DFA recognizing a generalized word-definite language must be nearly acyclic.
Description
Citation
Publisher
License
Attribution-NonCommercial 3.0 United States
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 and may not be copied or reproduced except as permitted by the Copyright Act or with permission from the copyright owner.
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 and may not be copied or reproduced except as permitted by the Copyright Act or with permission from the copyright owner.