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. \begin{equation} \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, \end{equation} 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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.