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.

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

Email this document to