Please use this identifier to cite or link to this item:
Nondeterministic Finite State Complexity
|Title:||Nondeterministic Finite State Complexity|
|Contributors:||Kjos-Hanssen, Bjørn (instructor)|
|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.|
|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 email@example.com if you need this content in ADA-compliant format.
Items in ScholarSpace are protected by copyright, with all rights reserved, unless otherwise indicated.