Can multipebble automata decide all deterministic context-sensitive languages?

Question

A MPA (multipebble automaton) is a 2DFA (two-way deterministic finite automaton) that can use arbitrary number of pebbles (actually at most $ |w|+2 $ pebbles on a given input $ w $ - the input is written on the tape between two end-markers as $ \# w \# $ ). During the computation, a MPA can detect whether the symbol under the head has a pebble, and then it can put a pebble (remove the pebble) if there is no pebble (a pebble).

$ h_k(\sigma) = \underbrace{\sigma \cdots \sigma}_{k \mbox{ times}} = \sigma^k $ is a homomorphism, where $ \sigma $ is a symbol and $ k>0 $.

For any deterministic context-sensitive language $ \mathtt{L} ~~ \left( \mathtt{L} \in \mathsf{DSPACE(n)} \right), $ it is not hard to show that there exists a $ k>0~ $ such that $ h_k( \mathtt{L} ) $ can be recognized by a MPA. So, loosely speaking, we can say that

any "problem" decidable by a linear-space DTM (deterministic Turing machine) can be decidable by a MPA.

Is it also true for any language in $ \mathsf{DSPACE(n)} $? Can MPAs decide all deterministic context-sensitive languages?

---

$ |w| $ is the length of $ w $.

$ w_i $ is the $ i^{th} $ symbol of $ w $, where $ 1 \leq i \leq |w| $.

$ h_k(\mathtt{L}) = \left\lbrace h_k(w_1) h_k(w_2) \cdots h_k(w_{|w|}) \mid w \in \mathtt{L} \right\rbrace $.

Answer 1

Perhaps you can build a language in DPSACE(n) that cannot be recognized by a MPA with $k=1$ using a diagonalization argument (probably the idea is similar to the one in Ben's answer, but I didn't dig into it):

Suppose that over alphabet $\Sigma = \{0,1\}$ you encode a MPA using a list of transitions:

$s,a,p \rightarrow s',p',L|R;...\#$

where $s$ is the current state, $a$ is the current symbol, $p$ is the pebble status, $s'$ is the new state, $p'$ is the new pebble state, $L|R$ is the move direction, $\#$ is an endmarker).

A Turing machine $M$ on input $x$ can check if it is a valid description of a $MPA_x$ and simulate it on input $x$ for $4^{|x|}$ steps using $6|x|+\log|x|$ cells, stretching the input in this way:

 MPA description # MPA tape # curr_state # counter #

Where:

• MPA description is the original input string $x$ (has length $|x|$);
• MPA tape is the MPA tape representation: for every cell we can use 3 bits to store the head flag, pebble flag, and the (fixed) tape content (has length $3|x|$);
• curr_state store the current state of the MPA (has length $\log |x|$);
• counter is the simulation step counter that is update after each simulation step (has length $2|x|$).

If $MPA_x$ halts in $4^{|x|}$ steps then TM $M$ outputs the opposite (if it doesn't halt $M$ outputs 0).

For large enough $x > x_0$, the $4^{|x|}$ simulation steps are greater than $2^{|x|+2} |x| \log |x|$ which is greater than the length of a complete configuration description of $MPA_x$; in this way if the $MPA_x$ doesn't halt in $4^{|x|}$ steps then we are sure that it will loop forever.

Suppose that there is an $MPA_y$ that decides the same language $L$ of $M$, then it always halts and you can build a "bigger" $MPA_{y'}$ that decides the same language, with $y'>x_0$ (just add dum states).

By construction we have, $MPA_{y'}(y') = 1 - M(y') = 1 - MPA_{y'}(y')$ which is a contradiction.

Answer 2

No. Counterexample: the halting problem for MPAs is decidable in linear space: if the MPA has N states, we need |k|+2 bits of space to store the pebble locations, log N bits to store the current state and $\log(N(|k|+2))+|k|+2$ bits to store a counter; if the counter cycles, the simulated machine will never halt. This is linear in |k| (ignoring the O(N \log N) space required to describe the machine), as required.

Since this language is decidable in linear space, it is also expressible as a DCSL.