A Linear-Time On-Line Recognition Algorithm for ``Palstar''
Zvi Galil, Joel Seiferas · Journal of the ACM · 1978
Let P1 = {w ~ X*:w = w R, [w I > 1} be the set of all nontnvial pahndromes over X A hneartime on-hne recogmtmn algorithm is presented for P~ ("palstar") on a random-access machine with addmon and umform cost criterion Also presented are a hnear-tlme on-line recognmon algorithm for P~ on a muitltape Turmg machine and a recognition algorithm for Pt 2 on a two-way deterministic pushdown automaton.The correctness of these algorithms is based on new "cancellation iemmas" for the languages P~ and P~