Abstract
We introduce the notion of a set of prohibitions and give definitions of a complete set and a crucial word with respect to a given set of prohibitions. We consider three special sets which appear in different areas of mathematics and for each of them examine the length of a crucial word. One of these sets is proved to be incomplete. The problem of determining lengths of words that are free from a set of prohibitions is shown to be NP-complete, although the related problem of whether or not a given set of prohibitions is complete is known to be effectively solvable.
Original language | English |
---|---|
Pages (from-to) | 273-289 |
Number of pages | 17 |
Journal | Journal of Combinatorial Theory Series A |
Volume | 105 |
Issue number | 2 |
Early online date | 20 Feb 2004 |
DOIs | |
Publication status | Published - Feb 2004 |
Keywords
- abelian squares
- NP-completeness
- crucial words
- unavoidablity
- avoidability