Codes, orderings, and partial words
- 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: Codes play an important role in the study of the combinatorics of words. In this paper, we introduce pcodes that play a role in the study of combinatorics ofpartial words. Partial words are strings over a finite alphabet that may contain a number of “do not know” symbols. Pcodes are defined in terms of the compatibility relation that considers two strings over the same alphabet that are equal except for a number of insertions and/or deletions of symbols. We describe various ways of defining and analyzing pcodes. In particular, many pcodes can be obtained as antichains with respect to certain partial orderings. Using a technique related to dominoes, we show that the pcode property is decidable.
Codes, orderings, and partial words
PDF (Portable Document Format)
481 KB
Created on 3/30/2011
Views: 2147
Additional Information
- Publication
- Theoretical Computer Science, Vol. 329, 2004, pp 177-202.
- Language: English
- Date: 2004
- Keywords
- Word, Partial word, Partial ordering, Code, Antichain, Domino