A word is closed if it contains a factor that occurs both as a prefix and as a suffix but does not have internal occurrences. We show that any word of length n contains at least n+1 closed factors (i.e., factors that are closed words). We investigate the language L of words over the alphabet {a, b} containing exactly n + 1 closed factors. We show that a word belongs to L if and only if its closed factors and its palindromic factors coincide (and therefore the words in L are rich words). We also show that L coincides with the language of conjugates of words in a∗b∗.
Words with the Smallest Number of Closed Factors (extended abstract)
Liptak, Zsuzsanna
2012-01-01
Abstract
A word is closed if it contains a factor that occurs both as a prefix and as a suffix but does not have internal occurrences. We show that any word of length n contains at least n+1 closed factors (i.e., factors that are closed words). We investigate the language L of words over the alphabet {a, b} containing exactly n + 1 closed factors. We show that a word belongs to L if and only if its closed factors and its palindromic factors coincide (and therefore the words in L are rich words). We also show that L coincides with the language of conjugates of words in a∗b∗.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
