
arXiv: 1203.1203
handle: 11588/567527 , 10447/73729
Trapezoidal words are words having at most $n+1$ distinct factors of length $n$ for every $n\ge 0$. They therefore encompass finite Sturmian words. We give combinatorial characterizations of trapezoidal words and exhibit a formula for their enumeration. We then separate trapezoidal words into two disjoint classes: open and closed. A trapezoidal word is closed if it has a factor that occurs only as a prefix and as a suffix; otherwise it is open. We investigate open and closed trapezoidal words, in relation with their special factors. We prove that Sturmian palindromes are closed trapezoidal words and that a closed trapezoidal word is a Sturmian palindrome if and only if its longest repeated prefix is a palindrome. We also define a new class of words, \emph{semicentral words}, and show that they are characterized by the property that they can be written as $uxyu$, for a central word $u$ and two different letters $x,y$. Finally, we investigate the prefixes of the Fibonacci word with respect to the property of being open or closed trapezoidal words, and show that the sequence of open and closed prefixes of the Fibonacci word follows the Fibonacci sequence.
Accepted for publication in Theoretical Computer Science
FOS: Computer and information sciences, Formal Languages and Automata Theory (cs.FL), trapezoidal words, Rich words, ta111, Computer Science - Formal Languages and Automata Theory, Sturmian words; Trapezoidal words; Rich words; Closed words; Special factors; Palindromes; Enumerative formula, Sturmian words, 68R15, Theoretical Computer Science, F.4.3, FOS: Mathematics, Sturmian words; trapezoidal words; Rich words; Closed words, Mathematics - Combinatorics, Closed words, Combinatorics (math.CO), Computer Science(all)
FOS: Computer and information sciences, Formal Languages and Automata Theory (cs.FL), trapezoidal words, Rich words, ta111, Computer Science - Formal Languages and Automata Theory, Sturmian words; Trapezoidal words; Rich words; Closed words; Special factors; Palindromes; Enumerative formula, Sturmian words, 68R15, Theoretical Computer Science, F.4.3, FOS: Mathematics, Sturmian words; trapezoidal words; Rich words; Closed words, Mathematics - Combinatorics, Closed words, Combinatorics (math.CO), Computer Science(all)
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 14 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
