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

A. Evdokimov; Sergey Kitaev

doi:10.1016/j.jcta.2003.12.003

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

A. Evdokimov, Sergey Kitaev

Research output: Contribution to journal › Article › peer-review

16 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.

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	https://doi.org/10.1016/j.jcta.2003.12.003
Publication status	Published - Feb 2004

Keywords

abelian squares
NP-completeness
crucial words
unavoidablity
avoidability

Access to Document

10.1016/j.jcta.2003.12.003

Cite this

@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 = feb,

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",

publisher = "Academic Press Inc.",

number = "2",

}

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

SN - 0097-3165

VL - 105

SP - 273

EP - 289

JO - Journal of Combinatorial Theory Series A

JF - Journal of Combinatorial Theory Series A

IS - 2

ER -

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

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this