The complexity properties of probabilistic automata with isolated cut point (Q1102752)

A probabilistic automaton (PA) which accepts a language with e-isolated cut point 1/2 corresponds to a PA which computes with \((1/2-e)\) bounded error probability. Let \(P(L,e)\) be the minimal number of states of a PA necessary for accepting a language L with e-isolated cut point 1/2. It is shown that there are languages \(L^ k\), \(1<k<\infty\), and an infinite sequence of numbers \(0<e_ 1<e_ 2<...<\) such that for all \(i\geq 1\), \(P(L^ k,e_ i)/P(L^ k,e_{i+1})\to 0\) when \(k\to \infty\). It is also shown that the probabilistic recognition of the language \(W^ k\) is more effective than that of the \(L^ k\).