Please use this identifier to cite or link to this item:
http://hdl.handle.net/10125/29507Nondeterministic 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.
This item is licensed under a Creative Commons License
