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.

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

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.


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)}$."

The same result also appears in Petersen (2009).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.