Crucial Words and the Complexity of Some Extremal Problems for Sets of Prohibited Words

Details Crucial Words and the Complexity of Some Extremal Problems for Sets of Prohibited Words Crucial Words and the Complexity of Some Extremal Problems for Sets of Prohibited Words

2002-05-20

arxiv.org/abs/math/0205217v1

Mathematics

Combinatorics

16 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Crucial Words and the Complexity of Some Extremal Problems for Sets of Prohibited Words does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Crucial Words and the Complexity of Some Extremal Problems for Sets of Prohibited Words, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Crucial Words and the Complexity of Some Extremal Problems for Sets of Prohibited Words will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-242556