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:, 79Kb

Download from publisher:

Related www page: not available

Bibliography entry: BibTeX

See also: early version


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