# Can real-time deterministic multicounter automata recognize the marked palindrome language?

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.

• You can easily use a Kolmogorov complexity argument to prove that a DMCA cannot correctly recognize MPAL. – Marzio De Biasi Nov 18 '14 at 23:41
• Would it be possible to link to something about multi-counter and real-time automata? – Huck Bennett Nov 22 '14 at 22:13

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.
I realized that in Fischer, Meyer, and Rosenberg (1968) 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)}$."