ELibM mirror of EPTCS 63

Recurrent Partial Words

Francine Blanchet-Sadri
(University of North Carolina at Greensboro)
Aleksandar Chakarov
(University of Colorado at Boulder)
Lucas Manuelli
(Princeton University)
Jarett Schwartz
(Princeton University)
Slater Stich
(Princeton University)

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.

In Petr Ambrož, Štěpán Holub and Zuzana Masáková: Proceedings 8th International Conference Words 2011 (WORDS 2011), Prague, Czech Republic, 12-16th September 2011, Electronic Proceedings in Theoretical Computer Science 63, pp. 71–82.
Published: 17th August 2011.

ArXived at: http://dx.doi.org/10.4204/EPTCS.63.11 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org