6533b860fe1ef96bd12c394e
RESEARCH PRODUCT
On the Number of Closed Factors in a Word
Gabriele FiciGolnaz BadkobehZsuzsanna Liptáksubject
FOS: Computer and information sciencesClosed wordCombinatorics on wordsComplete returnFormal Languages and Automata Theory (cs.FL)Computer scienceComputer Science (all)Structure (category theory)Computer Science - Formal Languages and Automata TheoryCombinatorics on words Closed word Complete return Rich word Bitonic word68R15Theoretical Computer ScienceCombinatoricsPrefixCombinatorics on wordsRich wordBitonic wordFOS: MathematicsMathematics - CombinatoricsCombinatorics (math.CO)ArithmeticWord (computer architecture)Combinatorics on worddescription
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 $\Theta(n^{2})$ many distinct closed factors.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2015-01-01 |