A closed word (a.k.a. periodic-like word or complete first return) is a word whose longest border does not have internal occurrences, or, equivalently, whose longest repeated prefix is not right special.We investigate the structure of closed factors of words. We show that a word of length n contains at least n + 1 distinct closed factors, and characterize those words having exactly n + 1 closed factors. Furthermore, we show that a word of length n can contain Θ(n2) many distinct closed factors.
Badkobeh, G., Fici, G., Lipták, Z. (2015). On the Number of Closed Factors in a Word. In A.H. Dediu, E. Formenti, C. Martín-Vide, B. Truthe (a cura di), Language and Automata Theory and Applications. LATA 2015 (pp. 381-390). Springer Verlag [10.1007/978-3-319-15579-1_29].
On the Number of Closed Factors in a Word
FICI, Gabriele
;
2015-01-01
Abstract
A closed word (a.k.a. periodic-like word or complete first return) is a word whose longest border does not have internal occurrences, or, equivalently, whose longest repeated prefix is not right special.We investigate the structure of closed factors of words. We show that a word of length n contains at least n + 1 distinct closed factors, and characterize those words having exactly n + 1 closed factors. Furthermore, we show that a word of length n can contain Θ(n2) many distinct closed factors.
| File | Dimensione | Formato | |
|---|---|---|---|
|
On the Number of Closed Factors in a Word.pdf
Solo gestori archvio
Tipologia:
Versione Editoriale
Dimensione
843.4 kB
Formato
Adobe PDF
|
843.4 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
