Crucial words and the complexity of some extremal problems for sets of prohibited words

A. Evdokimov, Sergey Kitaev

Research output: Contribution to journal › Article

14 Citations (Scopus)

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.
LanguageEnglish
Pages273-289
Number of pages17
JournalJournal of Combinatorial Theory Series A
Volume105
Issue number2
Early online date20 Feb 2004
DOIs
Publication statusPublished - Feb 2004

Fingerprint

Extremal Problems
NP-complete problem

Keywords

  • abelian squares
  • NP-completeness
  • crucial words
  • unavoidablity
  • avoidability

Cite this

Evdokimov, A. ; Kitaev, Sergey. / Crucial words and the complexity of some extremal problems for sets of prohibited words. In: Journal of Combinatorial Theory Series A . 2004 ; Vol. 105, No. 2. pp. 273-289.
@article{89fb557e3b37406e85b82d79c33b52d4,
title = "Crucial words and the complexity of some extremal problems for sets of prohibited words",
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.",
keywords = "abelian squares, NP-completeness, crucial words, unavoidablity, avoidability",
author = "A. Evdokimov and Sergey Kitaev",
year = "2004",
month = "2",
doi = "10.1016/j.jcta.2003.12.003",
language = "English",
volume = "105",
pages = "273--289",
journal = "Journal of Combinatorial Theory Series A",
issn = "0097-3165",
number = "2",

}

Evdokimov, A & Kitaev, S 2004, 'Crucial words and the complexity of some extremal problems for sets of prohibited words' 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.

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

T2 - Journal of Combinatorial Theory Series A

JF - Journal of Combinatorial Theory Series A

SN - 0097-3165

IS - 2

ER -

Evdokimov A, Kitaev S. Crucial words and the complexity of some extremal problems for sets of prohibited words. Journal of Combinatorial Theory Series A . 2004 Feb;105(2):273-289. https://doi.org/10.1016/j.jcta.2003.12.003

Access to Document