Please use this identifier to cite or link to this item:

Nondeterministic Finite State Complexity

File SizeFormat 
MA_2013_Hyde.pdf252.37 kBAdobe PDFView/Open

Item Summary

Title: Nondeterministic Finite State Complexity
Authors: Hyde, Kayleigh
Instructor: Kjos-Hanssen, Bjørn
Issue Date: 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
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
Appears in Collections:M.A. Plan B Theses- Mathematics Department

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