Please use this identifier to cite or link to this item: http://hdl.handle.net/10125/29507

Nondeterministic Finite State Complexity

File Size Format  
MA_2013_Hyde.pdf 252.37 kB Adobe PDF View/Open

Item Summary

Title:Nondeterministic Finite State Complexity
Authors:Hyde, Kayleigh
Contributors:Kjos-Hanssen, Bjørn (instructor)
Date Issued:2013
Publisher:University of Hawaii at Manoa
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.
Pages/Duration:33 pages
URI/DOI:http://hdl.handle.net/10125/29507
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.
Attribution-NonCommercial-NoDerivs 3.0 United States
http://creativecommons.org/licenses/by-nc-nd/3.0/us/
Appears in Collections: M.A. Plan B Theses- Mathematics Department


Please email libraryada-l@lists.hawaii.edu if you need this content in ADA-compliant format.

Items in ScholarSpace are protected by copyright, with all rights reserved, unless otherwise indicated.