6533b7d3fe1ef96bd1260a0b
RESEARCH PRODUCT
A Classification of Trapezoidal Words
Gabriele Ficisubject
FOS: Computer and information sciencesFormal Languages and Automata Theory (cs.FL)lcsh:Mathematicstrapezoidal words Sturmian words special factors palindromesPalindromeComputer Science - Formal Languages and Automata TheoryDisjoint setslcsh:QA1-939lcsh:QA75.5-76.95PrefixCombinatoricsF.4.3FOS: MathematicsMathematics - CombinatoricsCombinatorics (math.CO)lcsh:Electronic computers. Computer scienceSuffixWord (group theory)Mathematicsdescription
Trapezoidal words are finite words having at most n+1 distinct factors of length n, for every n>=0. They encompass finite Sturmian words. We distinguish trapezoidal words into two disjoint subsets: open and closed trapezoidal words. A trapezoidal word is closed if its longest repeated prefix has exactly two occurrences in the word, the second one being a suffix of the word. Otherwise it is open. We show that open trapezoidal words are all primitive and that closed trapezoidal words are all Sturmian. We then show that trapezoidal palindromes are closed (and therefore Sturmian). This allows us to characterize the special factors of Sturmian palindromes. We end with several open problems.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2011-08-17 |