# The best known upper bound for two-way probabilistic finite automata with one-counter

It is known that the class of languages recognized by two-way deterministic finite automata with one-counter (2D1CAs) is a proper subset of $\mathsf{L}$ (deterministic log-space): A 2D1CA can run at most $O(n^2)$ steps if it halts on a given input, and there is a language in $\mathsf{L}$, i.e. $$\mathtt{DG} = \lbrace w_0 \ w_1 \ \cdots \ w_k \mid k \geq 1, w_{i \in \lbrace 0, \ldots, k \rbrace} \in \lbrace a,b\rbrace^* , \mbox{ and } w_0=w_i \mbox{ for some } 1 \leq i \leq k \rbrace,$$ which cannot be recognized by any 2D1CA (Duris and Galil, 1982).

What happens if such an automaton can use a coin?

More precisely, what is the best known upper bound for the class of languages recognized by two-way probabilistic finite automata with one-counter (2P1CAs) with bounded error?