Recognizing certain repetitions and reversals within strings

Abstract

Let P1 = {w ε Σ*:w = wR, |w| ≫ 1} be the set of all nontrivial palindromes over Σ. In Part I, we present a linear-time on-line recognition algorithm for P1* ("palstar") on a random-access machine with addition and uniform cost criterion. We also present a lineartime on-line recognition algorithm for P12 on a multitape Turing machine and a recognition algorithm for P12 on a two-way deterministic pushdown automaton. The correctness of these algorithms is based on new "cancellation lemmas" for the languages P1* and P12. In Part II, we present real-time recognition algorithms for the languages {wxyxz ε Σ*: |w|=r|x|, |y|=s|x|, |z|=t|x|} and {wxyxRz ε Σ*: |w|=r|x|, |y|=s|x|, |z|=t|x|} on multitape Turing machines, for arbitrary fixed r, s, and t.