Small size quantum automata recognizing some regular languages

Given a class {p(alpha) vertical bar alpha is an element of I} of stochastic events induced by M-state 1-way quantum finite automata (1 qfa) on alphabet Sigma, we investigate the size (number of states) of 1 qfa's that delta-approximate a convex linear combination of 1 {p(alpha) vertical bar alpha is an element of I}, and we apply the results to the synthesis of small size 1 qfa's. We obtain: An O((Md/delta(3)) log(2)(d/delta(2))) general size bound, where d is the Vapnik dimension of {p(x)(w) vertical bar w is an element of Sigma*} For commutative n-periodic events p on Sigma with vertical bar Sigma vertical bar = H, we prove an O((H log n/delta(2))) size bound for inducing a delta-approximation of 1/2 + 1/2p whenever parallel to F((p) over cap)parallel to(1) <= n(H), where F((p) over cap) is the discrete Fourier transform of (the vector (p) over cap associated with) p. If the characteristic function chi(L) of an n-periodic unary language L satisfies parallel to F (chi(L))parallel to(1) <= n, then is recognized with isolated cut-point by a 1 qfa with O(log n) states. Vice versa, if L is recognized with isolated cut-point by a 1 qfa with O(log n) state, then parallel to F (chi(L)))parallel to(1) = O(n log n). (c) 2005 Elsevier B.V. All rights reserved.