Sequences of symbols from a given alphabet are known as words. If symbols are unknown at some positions, then such sequences are known as partial words. Two partial words are said to be compatible when they agree in all positions where they are defined.

The expressiveness of a partial word can be related to the number of full words that its factors are compatible with. In this paper, the authors investigate the computational bounds on these counting problems. In addition to proving the complexity results, an algorithm to solve the problems is also proposed.

The paper starts by covering the preliminary facts in section 2, while also providing sufficient pointers to the related literature. Section 3 contains a series of results, the main contribution being the polynomial time reduction of the satisfiability problem into a decision problem that checks the existence of a word of a given length that is not compatible with any element of a set of partial words.

Section 4 considers hard counting problems that are not associated with hard decision problems. In section 5, the authors investigate the generalization of the problem. They show that for an alphabet of a given size, counting the distinct full words that are compatible with at least one factor of a given partial word is #P-complete.

Section 6 proposes a basic algorithm based on the inclusion-exclusion principle, which can be adapted to many of the counting problems addressed in the paper. The authors claim that the proposed approach is superior to an exhaustive search when the length of the partial words is not much smaller than the number of partial words that contain the unknown symbol.

Overall, this is a well-written and interesting paper. Some background in the related theory will be helpful in following the proofs, but that is not strictly necessary as the material is mostly self-sufficient and the organization of the contents is logical. For researchers, the paper offers descriptions of problems that are worth pursuing further.