6533b833fe1ef96bd129c2e9

RESEARCH PRODUCT

Open and Closed Prefixes of Sturmian Words

Alessandro De LucaGabriele Fici

subject

FOS: Computer and information sciencesSequenceFibonacci numberDiscrete Mathematics (cs.DM)Formal Languages and Automata Theory (cs.FL)Sturmian wordStructure (category theory)Sturmian wordInfinite productComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)Computer Science - Formal Languages and Automata Theory68R15CombinatoricsPrefixComputer Science::Discrete MathematicsCombinatorics on words Sturmian wordFOS: MathematicsMathematics - CombinatoricsClosed wordsCombinatorics (math.CO)SuffixWord (group theory)Computer Science::Formal Languages and Automata TheoryMathematicsComputer Science - Discrete Mathematics

description

A word is closed if it contains a proper factor that occurs both as a prefix and as a suffix but does not have internal occurrences, otherwise it is open. We deal with the sequence of open and closed prefixes of Sturmian words and prove that this sequence characterizes every finite or infinite Sturmian word up to isomorphisms of the alphabet. We then characterize the combinatorial structure of the sequence of open and closed prefixes of standard Sturmian words. We prove that every standard Sturmian word, after swapping its first letter, can be written as an infinite product of squares of reversed standard words.

yearjournalcountryeditionlanguage
2013-06-10
10.1007/978-3-642-40579-2_15http://arxiv.org/abs/1306.2254