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

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
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

Please email if you need this content in ADA-compliant format.

This item is licensed under a Creative Commons License Creative Commons