Zapiski Nauchnykh Seminarov POMI, Theoretical application of methods of mathematical logic. Part II, Tome 68 (1977), pp. 123-139
Citer cet article
A. O. Slisenko. A simplified proof of the real-time recognizability of palindromes on turing machines. Zapiski Nauchnykh Seminarov POMI, Theoretical application of methods of mathematical logic. Part II, Tome 68 (1977), pp. 123-139. http://geodesic.mathdoc.fr/item/ZNSL_1977_68_a9/
@article{ZNSL_1977_68_a9,
author = {A. O. Slisenko},
title = {A simplified proof of the real-time recognizability of palindromes on turing machines},
journal = {Zapiski Nauchnykh Seminarov POMI},
pages = {123--139},
year = {1977},
volume = {68},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/ZNSL_1977_68_a9/}
}
TY - JOUR
AU - A. O. Slisenko
TI - A simplified proof of the real-time recognizability of palindromes on turing machines
JO - Zapiski Nauchnykh Seminarov POMI
PY - 1977
SP - 123
EP - 139
VL - 68
UR - http://geodesic.mathdoc.fr/item/ZNSL_1977_68_a9/
LA - ru
ID - ZNSL_1977_68_a9
ER -
%0 Journal Article
%A A. O. Slisenko
%T A simplified proof of the real-time recognizability of palindromes on turing machines
%J Zapiski Nauchnykh Seminarov POMI
%D 1977
%P 123-139
%V 68
%U http://geodesic.mathdoc.fr/item/ZNSL_1977_68_a9/
%G ru
%F ZNSL_1977_68_a9
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.
