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

A. Evdokimov, Sergey Kitaev

Research output: Contribution to journalArticle

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.
Original languageEnglish
Pages (from-to)273-289
Number of pages17
JournalJournal of Combinatorial Theory Series A
Volume105
Issue number2
Early online date20 Feb 2004
DOIs
Publication statusPublished - Feb 2004

Keywords

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

Fingerprint Dive into the research topics of 'Crucial words and the complexity of some extremal problems for sets of prohibited words'. Together they form a unique fingerprint.

  • Cite this