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.