De bruijn partial words
- UNCG Author/Contributor (non-UNCG co-authors, if there are any, appear on document)
- Benjamin J. Wyatt (Creator)
- Institution
- The University of North Carolina at Greensboro (UNCG )
- Web Site: http://library.uncg.edu/
- Advisor
- 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?
De bruijn partial words
PDF (Portable Document Format)
6626 KB
Created on 5/1/2013
Views: 2782
Additional Information
- Publication
- Thesis
- Language: English
- Date: 2013
- Keywords
- Combinatorics, De bruijn words, Partial words, String theory
- Subjects
- Combinatorial analysis
- Mathematical analysis