<p>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):<br>  </p>

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

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

<p>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).</p>

<p>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:</p>

<pre><code> MPA description # MPA tape # curr_state # counter #
</code></pre>

<p>Where:</p>

<ul>
<li>MPA description is the original input string $x$ (has length $|x|$);</li>
<li>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|$);</li>
<li>curr_state store the current state of the MPA (has length $\log |x|$);</li>
<li>counter is the simulation step counter that is update after each simulation step (has length $2|x|$).</li>
</ul>

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

<p>For large enough $x &gt; 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.</p>

<p>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'&gt;x_0$ (just add dum states).</p>

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

CC BY-SA 3.0
2014-11-23T23:38:54.737Z
Yeah, that's the argument I had in mind.
Ben Standeven
CC BY-SA 3.0
2014-11-06T00:47:39.837Z
2014-11-06T09:10:52.933Z
2014-11-06T09:10:52.933Z
Marzio De Biasi
<p>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.</p>

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

CC BY-SA 3.0
2014-11-05T13:30:42.150Z
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
CC BY-SA 3.0
2014-11-04T23:31:11.953Z
2014-11-04T23:31:11.953Z
Ben Standeven
<p>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).</p>

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

<p>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</p>

<blockquote>
  <p>any "problem" decidable by a linear-space DTM (deterministic Turing machine) can be decidable by a MPA.</p>
</blockquote>

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

<hr>

<p>$ |w| $ is the length of $ w $.</p>

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

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

CC BY-SA 3.0
2012-05-04T01:54:25.320Z
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
CC BY-SA 3.0
2012-05-04T13:44:35.743Z
@vzn: CSLs that are in DSPACE(n) are called deterministic CSLs, and they form exactly DSPACE(n).
Abuzer Yakaryilmaz
CC BY-SA 3.0
2012-05-05T22:00:32.027Z
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](http://cstheory.stackexchange.com/questions/1079/ntimenk-dtimenk/9676#9676) building on the PPST result. another problem I intuituively think is related is the problem of [compression of a TM run sequence](http://mathoverflow.net/questions/86339/compression-of-a-turing-machine-run-sequence)
vzn
CC BY-SA 3.0
2012-05-06T18:07:30.310Z
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
CC BY-SA 3.0
2012-05-06T19:39:31.093Z
@vzn: I do not say that **MPAs can decide all deterministic CSLs** in highlighted text! I prefer to use term **"problem"**, not the language. It also starts with **loosely speaking**. I mean, for example, that SUBSET-SUM problem can be associated with more than one language, and some of them can be decidable by MPAs.
Abuzer Yakaryilmaz
CC BY-SA 3.0
2012-05-06T20:21:28.850Z
then maybe you seem to be referring to computing _functions_ instead of decidable/decision problems or languages, true? however the way the subset sum problem is usually stated, afaik, is as a decision problem...true?
vzn
CC BY-SA 3.0
2014-11-04T23:33:57.123Z
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
<cc.complexity-theory><reference-request><automata-theory><space-bounded>
Can multipebble automata decide all deterministic context-sensitive languages?
Abuzer Yakaryilmaz
# Can multipebble automata decide all deterministic context-sensitive languages?

(Asked by: username_0 on 2012-05-03)

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

**Tags:** cc.complexity-theory, reference-request, automata-theory, space-bounded

> **Comments:**
> **username_1**: 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).  
> **username_0**: @username_1: CSLs that are in DSPACE(n) are called deterministic CSLs, and they form exactly DSPACE(n).  
> **username_1**: 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](http://cstheory.stackexchange.com/questions/1079/ntimenk-dtimenk/9676#9676) building on the PPST result. another problem I intuituively think is related is the problem of [compression of a TM run sequence](http://mathoverflow.net/questions/86339/compression-of-a-turing-machine-run-sequence)  
> **username_1**: 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)?  
> **username_0**: @username_1: I do not say that **MPAs can decide all deterministic CSLs** in highlighted text! I prefer to use term **"problem"**, not the language. It also starts with **loosely speaking**. I mean, for example, that SUBSET-SUM problem can be associated with more than one language, and some of them can be decidable by MPAs.  
> **username_1**: then maybe you seem to be referring to computing _functions_ instead of decidable/decision problems or languages, true? however the way the subset sum problem is usually stated, afaik, is as a decision problem...true?  
> **username_2**: 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$?  

---

## 2 answers

### Answer by username_3 on 2014-11-06. Score: 3 | Accepted answer

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.

> **Comments:**
> **username_2**: Yeah, that's the argument I had in mind.  

---

### Answer by username_2 on 2014-11-04. Score: 3

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.

> **Comments:**
> **username_0**: 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!!!  

---

