RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. LOMI, 1977 Volume 68, Pages 123–139 (Mi znsl2005)

This article is cited in 3 papers

A simplified proof of the real-time recognizability of palindromes on turing machines

A. O. Slisenko


Abstract: A comparatively short proof is given of the recognizability of palindromes in real time on multitape Turing machines. It is based on the same idea as the original proof by the author, and on Z. Galil's idea for simplifying the proof by using the Fischer–Paterson algorithm for finding all symmetric suffixes in linear time.

UDC: 51.01:518.5


 English version:
Journal of Soviet Mathematics, 1981, 15:1, 68–77

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025