On unavoidable sets of word patterns

Details On unavoidable sets of word patterns On unavoidable sets of word patterns

2003-11-23

arxiv.org/abs/math/0311399v1

Mathematics

Combinatorics

AMS-LaTeX, 13 pages, 4 figures

Scientific paper

We introduce the notion of unavoidable (complete) sets of word patterns, which is a refinement for that of words, and study certain numerical characteristics for unavoidable sets of patterns. In some cases we employ the graph of pattern overlaps introduced in this paper, which is a subgraph of the de Bruijn graph and which we prove to be Hamiltonian. In other cases we reduce a problem under consideration to known facts on unavoidable sets of words. We also give a relation between our problem and intensively studied universal cycles, and prove there exists a universal cycle for word patterns of any length over any alphabet. Keywords: pattern, word, (un)avoidability, de Bruijn graph, universal cycles

Affiliated with

Also associated with

No associations

Rating

On unavoidable sets of word patterns 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 On unavoidable sets of word patterns, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On unavoidable sets of word patterns will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-495564