AUTOMATICITY .1. PROPERTIES OF A MEASURE OF DESCRIPTIONAL COMPLEXITY

Let Sigma and Delta be nonempty alphabets with Sigma finite. Let f be a function mapping Sigma to Delta. We explore the notion of automatic ity, which attempts to model how ''close'' iis to a finite-state funct ion. Formally, the automaticity of f is a function A(f) (n) which coun ts the minimum number of states in any deterministic finite automaton that computes f correctly on all strings of length less than or equal to n (and its behavior on longer strings is not specified). We define A(L) (n) for languages L to be A(XL) (n), where X(L) is the characteri stic function of L. The same or similar notions were examined previous ly by Trakhtenbrot, Grinberg and Korshunov, Karp, Breitbart, Gabarro, Dwork and Stockmeyer, and Kaneps and Freivalds. Karp proved that if L subset of or equal to Sigma is not regular, then A(L)(n) greater than or equal to (n + 3)/2 infinitely often. We prove that the lower bound is best possible. We obtain results on the growth rate of A(f)(n). If \Sigma\ = k greater than or equal to 2 and \Delta\ = I < infinity, th en A(f)(n) less than or equal to C(1 + o(1)) k(n + 2)/n for C = (log(k ) l)/(k - 1)(2). Also, for almost all functions land any epsilon > 0 w e have A(f)(n) > (1 - epsilon) Ck(n + 1)/n for all sufficiently large n. We also obtain bounds on N-L(n), the nondeterministic automaticity function. This is similar to A(f)(n), except that it counts the number of states in the minimal NFA, and it is defined for languages L subse t of or equal to Sigma. For \Sigma\ = k greater than or equal to 2, w e have N-L(n) = O(k(n/2)). Also, for almost all languages L and every epsilon > 0 we have N-L(n) > (1 - epsilon) k(n/2)/root k - 1 for all s ufficiently large n. We prove some incomparability results between the automaticity measure and those defined earlier by Gabarro and others. Finally, we examine the notion of automaticity as applied to sequence s. (C) 1996 Academic Press, Inc.