Can multipebble automata decide all deterministic context-sensitive languages? 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&gt;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&gt;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 $.
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.