Partial word

For example, aab.ab.b is a partial word of length 8 over the alphabet A ={a,b} in which the fourth and seventh characters are holes.

[1] Several algorithms have been developed for the problem of "string matching with don't cares", in which the input is a long text and a shorter partial word and the goal is to find all strings in the text that match the given partial word.

[2][3][4] Two partial words are said to be compatible when they have the same length and when every position that is a non-wildcard in both of them has the same character in both.

This graph-theoretical interpretation of compatibility of partial words plays a key role in the proof of hardness of approximation of the clique problem, in which a collection of partial words representing successful runs of a probabilistically checkable proof verifier has a large clique if and only if there exists a valid proof of an underlying NP-complete problem.

over a binary alphabet, whose symbols are the Cartesian coordinates of the hypercube vertices (e.g., 0 or 1 for a unit cube).