<p>It doesn't seem to be possible and the reason looks simple (but I might overlook details).</p>

<p>After reading $w$ the number of reachable configurations of a real-time automaton is a polynomial in the lenght of $w$, whereas the number of different strings $w$ is exponential.</p>

CC BY-SA 3.0
2014-11-18T23:00:12.833Z
2014-11-18T23:00:12.833Z
Hendrik Jan
<p>I realized that in <a href="http://link.springer.com/article/10.1007%2FBF01694011#page-1" rel="nofollow">Fischer, Meyer, and Rosenberg (1968)</a> Theorem 1.3, it is proven that "The language of marked palindrome is not recognizable by any one-way $k-CM$ which operates in time less than $T(n) = 2^{(n/2k)}$." </p>

<p>The same result also appears in <a href="http://link.springer.com/chapter/10.1007/978-3-642-02737-6_33" rel="nofollow">Petersen (2009)</a>.</p>

CC BY-SA 3.0
2014-12-01T21:46:02.817Z
2014-12-01T21:46:02.817Z
Özlem Salehi
<p>Consider the marked palindrome language which is defined as MPAL=$\{ w\#w^r | w \in \{a,b\}^* \}$. </p>

<p>It is easy to recognize MPAL using only a single stack. </p>

<p>My question is whether MPAL can be recognized by a real-time deterministic multicounter automaton.  </p>

CC BY-SA 3.0
2014-11-18T23:41:15.467Z
You can easily use a Kolmogorov complexity argument to prove that a DMCA cannot correctly recognize MPAL.
Marzio De Biasi
CC BY-SA 3.0
2014-11-22T22:13:27.380Z
Would it be possible to link to something about multi-counter and real-time automata?
Huck Bennett
<reference-request><fl.formal-languages><automata-theory><counter-automata>
Can real-time deterministic multicounter automata recognize the marked palindrome language?
Özlem Salehi
# Can real-time deterministic multicounter automata recognize the marked palindrome language?

(Asked by: username_0 on 2014-11-18)

Consider the marked palindrome language which is defined as MPAL=$\{ w\#w^r | w \in \{a,b\}^\* \}$.

It is easy to recognize MPAL using only a single stack.

My question is whether MPAL can be recognized by a real-time deterministic multicounter automaton.

**Tags:** reference-request, fl.formal-languages, automata-theory, counter-automata
> **Comments:**
> **username_1**: You can easily use a Kolmogorov complexity argument to prove that a DMCA cannot correctly recognize MPAL.  
> **username_2**: Would it be possible to link to something about multi-counter and real-time automata?  

---

## 2 answers

### Answer by username_3 on 2014-11-18. Score: 2 | Accepted answer

It doesn't seem to be possible and the reason looks simple (but I might overlook details).

After reading $w$ the number of reachable configurations of a real-time automaton is a polynomial in the lenght of $w$, whereas the number of different strings $w$ is exponential.


---

### Answer by username_0 on 2014-12-01. Score: 4

I realized that in [Fischer, Meyer, and Rosenberg (1968)](http://link.springer.com/article/10.1007%2FBF01694011#page-1) Theorem 1.3, it is proven that "The language of marked palindrome is not recognizable by any one-way $k-CM$ which operates in time less than $T(n) = 2^{(n/2k)}$."

The same result also appears in [Petersen (2009)](http://link.springer.com/chapter/10.1007/978-3-642-02737-6_33).


---

