pcodes of partial words
by Visit the home page of F. Blanchet-Sadri.  and Margaret Moorefield


Codes play an important role in the study of combinatorics on words. Recently, we introduced pcodes that play a role in the study of combinatorics on partial words. Partial words are strings over a finite alphabet that may contain a number of “do not know” symbols. In this paper, the theory of codes of words is revisited starting from pcodes of partial words. We present some important properties of pcodes. We give several equivalent definitions of pcodes and the monoids they generate. We investigate in particular the Defect Theorem for partial words. We describe an algorithm to test whether or not a finite set of partial words is a pcode. We also discuss two-element pcodes, complete pcodes, maximal pcodes, and the class of circular pcodes.

Keywords:   Partial word, pcode, monoid, complete pcode, maximal pcode, circular pcode.

Visit the NSF homepage.

Acknowledgement:   This material is based upon work supported by the National Science Foundation under Grant No. CCF-0207673.

Disclaimer:   Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.

Visit the Partial Words homepage.