Rich partial words: Theory and applications

Abstract

Partial words are sequences over a finite alphabet that may include a wildcard symbol representing an unknown character. Rich partial words are a subclass characterized by their maximal palindromic richness. This paper provides a formal study of rich partial words, exploring their combinatorial properties, structural characteristics, and applications. We demonstrate their utility in error correction codes by leveraging their unique ability to handle ambiguities and their inherent structural redundancy for efficient error detection and correction.