Computer Science – Discrete Mathematics
Scientific paper
2011-08-18
EPTCS 63, 2011, pp. 71-82
Computer Science
Discrete Mathematics
In Proceedings WORDS 2011, arXiv:1108.3412
Scientific paper
10.4204/EPTCS.63.11
Partial words are sequences over a finite alphabet that may contain wildcard symbols, called holes, which match or are compatible with all letters; partial words without holes are said to be full words (or simply words). Given an infinite partial word w, the number of distinct full words over the alphabet that are compatible with factors of w of length n, called subwords of w, refers to a measure of complexity of infinite partial words so-called subword complexity. This measure is of particular interest because we can construct partial words with subword complexities not achievable by full words. In this paper, we consider the notion of recurrence over infinite partial words, that is, we study whether all of the finite subwords of a given infinite partial word appear infinitely often, and we establish connections between subword complexity and recurrence in this more general framework.
Blanchet-Sadri Francine
Chakarov Aleksandar
Manuelli Lucas
Schwartz Jarett
Stich Slater
No associations
LandOfFree
Recurrent Partial Words does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Recurrent Partial Words, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Recurrent Partial Words will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-180583