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 $.