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
Files
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
MA_2013_Hyde.pdf
Size:
252.37 KB
Format:
Adobe Portable Document Format
Description:
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.62 KB
Format:
Item-specific license agreed upon to submission
Description: