Erich P. Stuntebeck, John S. Davis II, et al.
HotMobile 2008
Let P1 = {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.
Erich P. Stuntebeck, John S. Davis II, et al.
HotMobile 2008
Pradip Bose
VTS 1998
Raymond Wu, Jie Lu
ITA Conference 2007
Ehud Altman, Kenneth R. Brown, et al.
PRX Quantum