2002/05/20 by A. Evdokimov, A. A. Evdokimov, Evdokimov, A. +3 · 1 citation
Computer Science · Mathematics · #Coding theory and cryptography #Computability, Logic, AI Algorithms #math.CO #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.math/0205217
16 pages
arxiv created 2002/05/20 · arxiv updated 2009/11/30
We introduced the notation 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 3 particular 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.