@Article{         so45804,
  Author        = "{Rudnicki}, P. and {Woeginger}, G.J.",
  Abstract      = "unary alphabet. We show that the complexity of this problem heavily depends on the representation of the input: the problem is NP-complete if the input is given in compact (logarithmic) form, whereas it becomes polynomially solvable if the input is encoded in unary.",
  date-added    = "2013-10-05 18:14:47 +0000",
  date-modified = "2013-10-05 18:14:47 +0000",
  Journal       = "Applied Mathematics Letters",
  Keywords      = "Post correspondence problem; Computational complexity; NP-complete; Pseudopolynomial time algorithm",
  Month         = "July",
  Number        = "5",
  Pages         = "723--727",
  Publisher     = "Pergamon",
  Title         = "The Post correspondence problem over a unary alphabet",
  URL           = "http://doc.utwente.nl/45804/",
  Volume        = "16",
  Year          = "2003",
  bdsk-url-1    = "http://www.sciencedirect.com/science/article/pii/S0893965903000739",
  bdsk-url-2    = "http://doc.utwente.nl/45804/",
  File          = "The Post correspondence problem over a unary alphabet - Rudnicki, Woeginger (0) (0) - a - a - j.pdf"
}

@Article{ so45804, Author = "{Rudnicki}, P. and {Woeginger}, G.J.", Abstract = "unary alphabet. We show that the complexity of this problem heavily depends on the representation of the input: the problem is NP-complete if the input is given in compact (logarithmic) form, whereas it becomes polynomially solvable if the input is encoded in unary.", date-added = "2013-10-05 18:14:47 +0000", date-modified = "2013-10-05 18:14:47 +0000", Journal = "Applied Mathematics Letters", Keywords = "Post correspondence problem; Computational complexity; NP-complete; Pseudopolynomial time algorithm", Month = "July", Number = "5", Pages = "723--727", Publisher = "Pergamon", Title = "The Post correspondence problem over a unary alphabet", URL = "http://doc.utwente.nl/45804/", Volume = "16", Year = "2003", bdsk-url-1 = "http://www.sciencedirect.com/science/article/pii/S0893965903000739", bdsk-url-2 = "http://doc.utwente.nl/45804/", File = "The Post correspondence problem over a unary alphabet - Rudnicki, Woeginger (0) (0) - a - a - j.pdf" }