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

• interesting question; intend to post some loosely related refs that may be relevant if nobody else comes up with something better/closer. a question though. CSLs that are in DSpace(n) are not necessarily the same as all linear-space DTMs, right? actually that is an open question right? or closely related to one? because CSLs are proven to be equal to NSpace(n) and its open if NSpace(n) == DSpace(n). – vzn May 4 '12 at 1:54
• @vzn: CSLs that are in DSPACE(n) are called deterministic CSLs, and they form exactly DSPACE(n). – Abuzer Yakaryilmaz May 4 '12 at 13:44
• ok. the ref I had in mind as "probably related" is the pebbling arguments used to attack the DTime(n^k)=?Ntime(n^k) question eg recent results of Santhanam building on the PPST result. another problem I intuituively think is related is the problem of compression of a TM run sequence – vzn May 5 '12 at 22:00
• can you plz clarify the question somewhat? didnt you just assert in the highlighted text that MPAs can decide all deterministic CSLs? eg is there some way to rephrase your question in terms of h_k(L)? – vzn May 6 '12 at 18:07
• The theorem is that if $\sigma$ is a DCSL, there is some $k$ such that $h_k(\sigma)$ can be computed by an MPA. The question is, can we take $k=1$? – Ben Standeven Nov 4 '14 at 23:33

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.

• Yeah, that's the argument I had in mind. – Ben Standeven Nov 23 '14 at 23:38

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.

• Maybe I am missing some simple points but I could not get how your counterexample works. Could you please more descriptive about how your argument works? Thanks!!! – Abuzer Yakaryilmaz Nov 5 '14 at 13:30