Number of Holes in Unavoidable Sets of Partial Words I
- UNCG Author/Contributor (non-UNCG co-authors, if there are any, appear on document)
- Francine Blanchet-Sadri, Professor (Creator)
- Institution
- The University of North Carolina at Greensboro (UNCG )
- Web Site: http://library.uncg.edu/
Abstract: Partial words are sequences over a finite alphabet that may contain some undefined positions called holes. We consider unavoidable sets of partial words of equal length. We compute the minimum number of holes in sets of size three over a binary alphabet (summed over all partial words in the sets). We also construct all sets that achieve this minimum. This is a step towards the difficult problem of fully characterizing all unavoidable sets of partial words of size three.
Number of Holes in Unavoidable Sets of Partial Words I
PDF (Portable Document Format)
338 KB
Created on 6/26/2014
Views: 1602
Additional Information
- Publication
- Journal of Discrete Algorithms, 14, 55-64
- Language: English
- Date: 2014
- Keywords
- Automata and formal languages, Combinatorics on words, Partial words, Unavoidable sets