Paper by Erik D. Demaine

Reference:

Therese C. Biedl, Jonathan F. Buss, Erik D. Demaine, Martin L. Demaine, Mohammadtaghi Hajiaghayi, and Tomáš Vinař, “Palindrome Recognition Using a Multidimensional Tape”, Theoretical Computer Science, volume 302, number 1–3, June 2003, pages 475–480.

BibTeX

@Article{Palindromes_TCS,
  AUTHOR        = {Therese C. Biedl and Jonathan F. Buss and Erik D. Demaine
                   and Martin L. Demaine and Mohammadtaghi Hajiaghayi and
                   Tom\'a\v{s} Vina\v{r}},
  TITLE         = {Palindrome Recognition Using a Multidimensional Tape},
  JOURNAL       = {Theoretical Computer Science},
  journalurl    = {https://www.journals.elsevier.com/theoretical-computer-science},
  VOLUME        = 302,
  NUMBER        = {1--3},
  MONTH         = {June},
  YEAR          = 2003,
  PAGES         = {475--480},

  length        = {7 pages},
  doi           = {https://dx.doi.org/10.1016/S0304-3975(03)00086-0},
  dblp          = {https://dblp.org/rec/journals/tcs/BiedlBDDHV03},
  comments      = {This paper is also available from <A HREF="http://dx.doi.org/10.1016/S0304-3975(03)00086-0">ScienceDirect</A>.},
}

Abstract:

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

Comments:

This paper is also available from ScienceDirect.

Length:

The paper is 7 pages.

Availability:

The paper is available in PostScript (80k), gzipped PostScript (32k), and PDF (123k).

See information on file formats.

[Google Scholar search]