Let
and
be nonempty alphabets with
finite. Let
f be a function mapping
* to
. We explore the notion of
automaticity, which attempts to model how
close
f is to a finite-state function. Formally, the automaticity of
f is a function A
f(
n) which counts the minimum number of states in any deterministic finite automaton that computes
f correctly on all strings of length
n (and its behavior on longer strings is not specified). The same or similar notions were examined previously by Trakhtenbrot, Grinberg and Korshunov, Karp, Breitbart, Gabarró, Dwork and Stockmeyer, and Kaneps and Freivalds.
Research supported in part by NSERC.
Research supported in part by NSF grant #IRI-9221947.