Keller 403.

Title:  Non-deterministic Automatic Complexity of Fibonacci words

Abstract:  Automatic complexity rates can be thought of as a measure of how random words can be for some given automaton (machine). By creating a scale between 0 and 1 that ranges from predictable to complex, if the rate of a given word is strictly between 0 and 1/2  then we call it indeterminate. In this paper we show that for an infinite Fibonacci word the non-deterministic automatic complexity can be no greater than 1/Φ^2.