AUTOMATICITY .2. DESCRIPTIONAL COMPLEXITY IN THE UNARY CASE

Let Sigma and Delta be finite alphabets, and let f be a map from Sigma to Delta. Then the deterministic automaticity of f, A(f)(n), is defi ned to be the size of the minimum finite-state machine that correctly computes f on all inputs of size less than or equal to n. A similar de finition applies to languages L. We denote the nondeterministic analog ue (for languages L) of automaticity by N-L(n). In a previous paper, S hallit and Breitbart examined the properties of this measure of descri ptional complexity in the case \Sigma\ greater than or equal to 2. In this paper, we continue the study of automaticity, focusing on the cas e where \Sigma\ = 1. We prove that A(f)(n) less than or equal to n + 1 - [log(l)n], where l = \Delta\. We also prove that A(f)(n) > n - 2 lo g(l) n - 2 log(l)log(l) n for almost all functions f. In the nondeterm inistic case, we show that there exists a c such that for almost all u nary languages L, we have N-L(n) > cn/log n for all sufficiently large n. The proof is based on a nevi enumeration method for languages acce pted by unary q-state NFAs. If L is not a regular language, then it fo llows from a result of Karp that lim sup(n --> infinity) A(L)(n)/n gre ater than or equal to 1/2. We conjecture that if L subset of or equal to 0, then this bound can be improved to (root 5 - 1)/2. Finally, we give some lower bounds for nondeterministic automaticity for nonregula r languages.