Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
An Answer to a Conjecture on Overlaps in Partial Words Using Periodicity Algorithms
verfasst von : Francine Blanchet-Sadri, Robert Mercaş, Abraham Rashin, Elara Willett
Erschienen in: Language and Automata Theory and Applications
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We propose an algorithm that given as input a full word
w
of length
n
, and positive integers
p
and
d
, outputs (if any exists) a maximal
p
-periodic partial word contained in
w
with the property that no two holes are within distance
d
. Our algorithm runs in
O
(
nd
) time and is used for the study of freeness of partial words. Furthermore, we construct an infinite word over a five-letter alphabet that is overlap-free even after the insertion of an arbitrary number of holes, answering affirmatively a conjecture from Blanchet-Sadri, Mercaş, and Scott.