$ (2^m x_1 y)^R[m] = x_1[i] = 1 $ and $ (2^m x_2 y)^R[m] = x_2[i] = 0 $. Thus, $ 2^m x_1 y \in {\mathtt{END}}$ and $ 2^m x_2 y \not\in {\mathtt{END}}$. Therefore, the configurations after reading $ 2^m x_1 $ and $ 2^m x_2 $ must be different. However, the number of possible configurations for a realtime DkCA after reading the partial input $ 2^m x $ is $ O(m) $ while there are $ 2^m $ possible $ x $’s. This is a contradiction.

Currently, we do not know any QCA algorithm solving $ {\mathtt{END}}$. Moreover, recently another promise problem solvable by exact QCAs but not by DCAs was introduced in [@NY15A] and we also do not know whether AfCAs can solve this promise problem.

Las Vegas algorithms
====================

In [@RasY14A], some promise problems were given in order to show the superiority of two-way QFAs (2QCFAs) over two-way PFAs (2PFAs). We show that the same problem can be solved by realtime Las Vegas AfAs or AfAs with restart in linear expected time.

First we review the results given in [@RasY14A]. Let $ {\mathtt{PAL}}= \{ w \in \{1,2\}^* \mid w = w^r \} $ be the language of 