Nondeterministic Finite State Complexity

Date
2013
Authors
Hyde, Kayleigh
Journal Title
Journal ISSN
Volume Title
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.
Description
Keywords
Citation
Rights
Access Rights
Email libraryada-l@lists.hawaii.edu if you need this content in ADA-compliant format.