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.