### Abstract

Language | English |
---|---|

Pages | 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

}

*Journal of Combinatorial Theory Series A*, vol. 105, no. 2, pp. 273-289. https://doi.org/10.1016/j.jcta.2003.12.003

**Crucial words and the complexity of some extremal problems for sets of prohibited words.** / Evdokimov, A.; Kitaev, Sergey.

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

T2 - Journal of Combinatorial Theory Series A

JF - Journal of Combinatorial Theory Series A

SN - 0097-3165

IS - 2

ER -