2
$\begingroup$

What is the simplest machine model accepting the following language?

$$ L = \{(w\# )^{k}\;|\; w\in \Sigma^{*},\;k\in \mathbb{N}\}$$

In other words, $L$ is obtained by taking each string $w$ in $\Sigma^*$, and then creating the strings $w\#\;,\; w\#w\#\;,\; w\#w\#w\#\;,...$

Here $\#$ is a separator symbol which is not in $\Sigma$.

The simplest I could think of was queue automata with $2$-queues. But these are already Turing complete. Is there some well studied class of machines that is not Turing complete and accepts $L$?

$\endgroup$
  • 3
    $\begingroup$ Why do you need two queues? Doesn't a single queue suffice? $\endgroup$ – Thomas Sep 21 '16 at 17:53
4
$\begingroup$

This language is in $ \mathsf{SL}^=_\mathbb{Q} $, the class of co-exclusive rational stochastic language (YS10). (More details were added below as Appendix 1!)

A language L is in $ \mathsf{SL}^=_\mathbb{Q} $ if there exists a probabilistic finite automaton (PFA) $P$ defined with only rational numbers such that every member is accepted by $P$ with probability $ 1 \over 2 $ and every non-member is accepted by $P$ with probability different than $ 1 \over 2 $.

$ \mathsf{SL}^=_\mathbb{Q} $ is also exactly characterized by

  • realtime universal quantum finite automata (you can think as the "complement" of realtime nondeterministic quantum automata (YS10)),
  • realtime deterministic blind vector automata (SYS13), and
  • realtime (negative) one-sided bounded-error affine automata (VY16), where all machines are defined with rational numbers.

Your language can also be recognized by realtime universal one-counter automaton and realtime private alternating finite automaton (DHRSY), deterministic set automata (KMW), and one-way deterministic 2-head finite automata.

Currently these are the ones that I could remember!


Appendix 1: More details on $ \mathsf{SL^=_\mathbb{Q}} $. Here I use another model, which is simpler than PFA to program in our case.

An $n$-state Turakainen finite automaton (TuFA) $ T $ is a 5 tuple $$ T = (S,\Sigma,\{A_\sigma \mid \sigma \in \Sigma\},v_0,f), $$ where

  • $ S = \{s_1,\ldots,s_n\}$ is the set of states,
  • $ \Sigma $ is the input alphabet,
  • $ A_\sigma \in \mathbb{Q}^{n \times n} $ is the transition matrix for symbol $ \sigma \in \Sigma $,
  • $ v_0 $ is the initial state, and
  • $ f $ is the final vector.

For a given input $ w \in \Sigma^* $, the accepting value of $ T $ on $ w $ is given by $$ f_T(w) = f A_{w_{|w|}} \cdots A_{w_2} A_{w_1} v_0, $$ where $ w_i $ is the $i$-th symbol of $ w $. (Remark that $ f_T(w) \in \mathbb{Q} $.) In the other words, $ T $ starts its computation in $ v_0 $ and then read $ w $ from the left to the right symbol by symbol and for each symbol it applies the corresponding transition matrix. At the end, it takes inner product of the final state with the final vector and it gives the accepting value (it can also be seen as a weighted sum of the entries in the final state).

There exists a TuFA $ T $ that defines the language $ L = \{ w \in \Sigma^* \mid f_T(w) = 0 \} $ if and only if $ L \in \mathsf{SL^=} $.

By using a TuFA, you can encode a binary string. Let $ w \in \{0,1\}^* $ be a given binary string and $ e(w) = 1w $ be its encoding.

The initial state is $ ( 1 ,1 ) $. For symbols 0 and 1, it applies the transition matrices $$ A_0 = \left( \begin{array}{cc} 1 & 0 \\ 2 & 0 \end{array} \right) \mbox{ and } A_1 = \left( \begin{array}{cc} 1 & 0 \\ 2 & 1 \end{array} \right), $$ respectively.

After reading $ w $, the new state vector is $ (1,e(w)) $. Then, if it reads symbol 0, then the new state becomes $ (1,2e(w)) = (1,e(w0)) $; and, if it reads symbol 1, then the new state becomes $ (1,2e(w)+1) = (1,e(w1)) $.

The language $ \mathtt{TWIN} = \{ w \# w \mid w \in \{0,1\}^* \} $ is in $ \mathsf{SL^=} $. We can design a TuFA using the above encoding. Let $ w_1 \# w_2 $ be the given input. Otherwise, set the accepting value to a nonzero value. Encode $ w_1 $ and $ w_2 $ in the values of two states and then set the accepting value to $ e(w_1) - e(w_2) $. Thus, $ f_T(w_1 \# w_2) = 0 $ if and only if $ w_1 = w_2 $.

If we tensor $ T $ with itself, then we can also set the accepting value to $ (e(w_1) - e(w_2))^2 $. In fact, one can easily play with different combinations.

Let $ \mathtt{COPIES} = \{ (w\#)^k \mid w \in \{0,1\}^*, k \geq 1 \} $. We design a TuFA $T$ for $ \mathtt{COPIES} $. It is trivial to detect $ k=1 $. Let $ w_1 \# w_2 \# \cdots \# w_k \# $ be the given input for some $ k >1 $. Encode $ w_1 $ into the value of a state and keep it until end of the computation. Also reserve the value of a state for the accepting values, which is zero at the beginning. After reading $ w_i $ ($ 2 \leq k \leq k $), add $ (e(w_1)-e(w_i))^2 $ to the accepting value. The accepting value ends with 0 for any member and with some positive integers for any non-member. More precisely, $$ f_T(w_1 \# w_2 \# \cdots \# w_k) = \sum_{i = 2}^k (e(w_1)-e(w_i))^2 $$.

Therefore, $ \mathtt{COPIES} $ is in $ \mathsf{SL^=} $.

$\endgroup$
  • $\begingroup$ thanks for your answer. But I have to admit that, except for the 2 head finite automata, I don't understand how the other models can be used to accept the language of the question. Would you be kind to add some comment on what do the $SL^=_Q$ machine does to accept the language? $\endgroup$ – verifying Oct 3 '16 at 22:01
  • $\begingroup$ I added some explanations for $ \mathsf{SL_\mathbb{Q}^=} $. I hope it would be sufficient to follow the missing details. $\endgroup$ – Abuzer Yakaryilmaz Oct 6 '16 at 16:24
5
$\begingroup$

Just to refine Abuzer's answer, the language can also be recognized by a Stateless 2-head 1-way DFA which is usually defined in this way [Ibarra et al., On stateless multihead automata: hierarchies and the emptiness problem (2010)]:

For an input string $w \in \Sigma$, machines work on a tape containing $\text{^} w \$$ and start with all heads on the left end marker. At every step of the computation, the symbols $a_1,..., a_k$ currently scanned by all $k$ heads are considered, any corresponding transition $a_1,...,a_k \to d_1,...,d_k \in \delta, a_i \in \Sigma \cup \{\text{^}, \$\}$ is chosen, and each $i$-th heads is moved according to $d_i \in \{ Stay, Right \}$. If no such transition exists, the automaton rejects. If any of the heads falls off the tape, the automaton rejects as well. If the transition instructs all heads to Stay, the automaton halts and accepts. The string is accepted if there exists a computation resulting in acceptance.

If $\Sigma = \{0,1,\#\}$, then your language is recognized by the following Stateless 2-head 1-way DFA:

   ^   ,  ^   -> S , R
   ^   ,{0,1} -> S , R
   ^   ,  #   -> R , R
   0   ,  0   -> R , R
   1   ,  1   -> R , R
   #   ,  #   -> R , R
{0,1,#},  $   -> S , S
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.