Nondeterministic Finite State Complexity
| dc.contributor.author | Hyde, Kayleigh | |
| dc.contributor.instructor | Kjos-Hanssen, Bjørn | |
| dc.date.accessioned | 2013-07-02T20:24:03Z | |
| dc.date.available | 2013-07-02T20:24:03Z | |
| dc.date.issued | 2013 | |
| dc.description.abstract | We define a new measure of complexity for finite strings using nondeterministic finite automata, called nondeterministic automatic complexity and denoted AN(x). In this paper we prove some basic results for AN(x), give upper and lower bounds, estimate it for some specific strings, begin to classify types of strings with small complexities, and provide AN(x) for |x| ≤ 8. | |
| dc.format.extent | 33 pages | |
| dc.identifier.uri | http://hdl.handle.net/10125/29507 | |
| dc.language.iso | en-US | |
| dc.publisher | University of Hawaii at Manoa | |
| dc.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. | |
| dc.rights | Attribution-NonCommercial-NoDerivs 3.0 United States | |
| dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/3.0/us/ | |
| dc.title | Nondeterministic Finite State Complexity | |
| dc.type | Thesis | |
| dc.type.dcmi | Text | |
| local.thesis.degreelevel | MA | |
| local.thesis.department | Mathematics |