Subword Complexity of Partial Words
F. Blanchet-Sadri
blanchet@uncg.edu
      Jarett Schwartz
      Slater Stich


Abstract


Subword complexity has become an important research topic in combinatorics on words. Application areas include dynamical systems, ergodic theory, and theoretical computer science. In these papers, we extend many of the central ideas on the complexity of full words to partial words, or sequences with wild card symbols. The subword complexity function of a finite or infinite partial word w over a given alphabet assigns to each positive integer n, the number of distinct full words over the alphabet that are compatible with factors of length n of w. Among other things, we investigate the question: ``Which functions may be the subword complexity of partial words.''

Keywords: Combinatorics on words; Partial words; Sturmian Words; Orders of Complexity; Saturation; Immunity; Representability.