Abstract
| 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 |
Fingerprint
Keywords
- abelian squares
- NP-completeness
- crucial words
- unavoidablity
- avoidability
Cite this
}
Crucial words and the complexity of some extremal problems for sets of prohibited words. / Evdokimov, A.; Kitaev, Sergey.
In: Journal of Combinatorial Theory Series A , Vol. 105, No. 2, 02.2004, p. 273-289.Research output: Contribution to journal › Article
TY - JOUR
T1 - Crucial words and the complexity of some extremal problems for sets of prohibited words
AU - Evdokimov, A.
AU - Kitaev, Sergey
PY - 2004/2
Y1 - 2004/2
N2 - 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.
AB - 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.
KW - abelian squares
KW - NP-completeness
KW - crucial words
KW - unavoidablity
KW - avoidability
UR - https://personal.cis.strath.ac.uk/sergey.kitaev/index_files/Papers/crucial_words.ps
U2 - 10.1016/j.jcta.2003.12.003
DO - 10.1016/j.jcta.2003.12.003
M3 - Article
VL - 105
SP - 273
EP - 289
JO - Journal of Combinatorial Theory Series A
JF - Journal of Combinatorial Theory Series A
SN - 0097-3165
IS - 2
ER -