Therese Biedl, Jonathan F. Buss, Erik D. Demaine, Martin L. Demaine, Mohammadtaghi Hajiaghayi, Tomas Vinar. Palindrome recognition using a multidimensional tape . Theoretical Computer Science, 302(1-3):475-480. 13 June 2003.

Download preprint: 03palindromes.ps, 79Kb

Download from publisher: http://dx.doi.org/10.1016/S0304-3975(03)00086-0

Related www page: not available

Bibliography entry: BibTeX

See also: early version

Abstract:

The problem of palindrome recognition using a Turing machine with one 
multidimensional tape is proved to require Theta(n^2/log n) time.

Last update: 10/01/2006