On the Distribution of Complexities of Finite Words, with Connections to Constructive Immunity
Date
2023
Authors
Contributor
Advisor
Department
Instructor
Depositor
Speaker
Researcher
Consultant
Interviewer
Narrator
Transcriber
Annotator
Journal Title
Journal ISSN
Volume Title
Publisher
Volume
Number/Issue
Starting Page
Ending Page
Alternative Title
Abstract
This thesis presents results on complexities of finite and infinite words, where ``complexity" is defined using finite state and Turing machines, respectively. Specifically, the complexity of a word $w$ is defined to be the minimum number of states in a finite state machine needed to uniquely output $w$ among all words of length $\abs{w}$. A theorem counting the number of words of length $n$ and deterministic hidden Markov model complexity $q$ is proven, giving insight into the distribution of deterministic hidden Markov model complexity. In particular, this theorem allows for the computation of deterministic hidden Markov model complexity in polynomial time, an improvement over the exponential-time naive computation. Non-deterministic hidden Markov models of various states are shown to be realized by deterministic hidden Markov models, and the strengths of languages defined by hidden Markov model complexity are investigated. Finally, analogs of these results are expanded to infinite words and to finite-state gambler complexity.
When discussing complexities of infinite words in the next topic, $\Sigma^0_1$ and constructively $\Sigma^0_1$ dense sets are introduced. It is shown that these classes are distinct and that they occur in non-$\Delta^0_2$ degrees, high degrees, and c.e. degrees. Then, connections from $\Sigma^0_1$ sets to a problem on the computable dense subsets of $\Q$ is established. Finally, results on effective notions of the complexities of finite words are presented, providing a link between the two topics.
Description
Keywords
Mathematics
Citation
Extent
Format
Geographic Location
Time Period
Related To
Related To (URI)
Table of Contents
Rights
All UHM dissertations and theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission from the copyright owner.
Rights Holder
Local Contexts
Collections
Email libraryada-l@lists.hawaii.edu if you need this content in ADA-compliant format.