Testing avoidability on sets of partial words is hard

Blanchet-Sadri, F.;Jungers, Raphaël;Palumbo, Justin
(2009) Theoretical Computer Science — Vol. 410, n° 8-10, p. 968-972 (2009)

Files

pdfdocument.pdf
  • Restricted Access
  • Adobe PDF
  • 332.68 KB
Request a copy

Details

Authors
Abstract
We prove that the problem of deciding whether a finite set of partial words is unavoidable is NP-hard for any alphabet of size larger than or equal to two, which is in contrast with the well-known feasability results for unavoidability of a set of full words. We raise some related questions on avoidability of sets of partial words. (C) 2008 Elsevier B.V. All rights reserved.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Blanchet-Sadri, F., Jungers, R., & Palumbo, J. (2009). Testing avoidability on sets of partial words is hard. Theoretical Computer Science, 410(8-10), 968-972. https://doi.org/10.1016/j.tcs.2008.11.011 (Original work published 2009)