De bruijn partial words

UNCG Author/Contributor (non-UNCG co-authors, if there are any, appear on document)
Benjamin J. Wyatt (Creator)
The University of North Carolina at Greensboro (UNCG )
Web Site:
Francine Blanchet-Sadri

Abstract: In a kn-complex word over an alphabet Σ of size k each of the kn words of length n appear as a subword at least once. Such a word is said to have maximum subword complexity. De Bruijn sequences of order n over Σ are the shortest words of maximum subword complexity and are well known to have length kn+n-1. They are efficiently constructed by finding Eulerian cycles in so-called de Bruijn graphs. In this thesis, we investigate partial words, or sequences with wildcard symbols or hole symbols, of maximum subword complexity. The subword complexity function of a partial word w over a given alphabet of size k assigns to each positive integer n, the number pw(n) of distinct full words over the alphabet that are compatible with factors of length n of w. For positive integers h, k and n, a de Bruijn partial word of order n with h holes over an alphabet Σ of size k is a partial word w with h holes over Σ of minimal length with the property that pw(n)=kn. In some cases, they are efficiently constructed by finding Eulerian paths in modified de Bruijn graphs. We are concerned with the following three questions: (1) What is the length of k-ary de Bruijn partial words of order n with h holes? (2) What is an efficient method for generating such partial words? (3) How many such partial words are there?

Additional Information

Language: English
Date: 2013
Combinatorics, De bruijn words, Partial words, String theory
Combinatorial analysis
Mathematical analysis

Email this document to