Some bounds on the complexity of predicate recognition by finite automata

摘要

Let p(n) be the smallest number such that some finite automaton with p(n) internal states exists which recognizes predicate P over the set of words of length not greater than n. Then there exists a predicate P defined on (0, 1)* such that an infinite sequence n1, n2,…,nk…, when nk→∞ as k→∞ can be constructed for which T(nk)∼ 2nk+2/nk, where T(x)=P(x) or P(xR), for xR is the reverse of x.