5
$\begingroup$

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.

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

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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