|
|||||
|
|
Testing avoidability on sets of partial words is hard |
|
| Authors: | F Blanchet-Sadri Raphaël M Jungers Justin Palumbo |
| Affiliation: | 1. Department of Computer Science, University of North Carolina, P.O. Box 26170, Greensboro, NC 27402–6170, USA;2. Department of Mathematical Engineering, Université catholique de Louvain, Avenue Georges Lemaitre 4, B–1348 Louvain-la-Neuve, Belgium;3. UCLA Mathematics Department, Box 951555, Los Angeles, CA 90095–1555, USA |
| 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. |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ | |