On the Distribution of Complexities of Finite Words, with Connections to Constructive Immunity
| dc.contributor.advisor | Kjos-Hanssen, Bjørn | |
| dc.contributor.author | Birns, Samuel | |
| dc.contributor.department | Mathematics | |
| dc.date.accessioned | 2023-07-11T00:20:15Z | |
| dc.date.available | 2023-07-11T00:20:15Z | |
| dc.date.issued | 2023 | |
| dc.description.degree | Ph.D. | |
| dc.identifier.uri | https://hdl.handle.net/10125/105075 | |
| dc.subject | Mathematics | |
| dc.title | On the Distribution of Complexities of Finite Words, with Connections to Constructive Immunity | |
| dc.type | Thesis | |
| dcterms.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. | |
| dcterms.language | en | |
| dcterms.publisher | University of Hawai'i at Manoa | |
| dcterms.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. | |
| dcterms.type | Text | |
| local.identifier.alturi | http://dissertations.umi.com/hawii:11810 |
Files
Original bundle
1 - 1 of 1
Loading...
- Name:
- Birns_hawii_0085A_11810.pdf
- Size:
- 686.05 KB
- Format:
- Adobe Portable Document Format