14
$\begingroup$

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?

$\endgroup$

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.