Enumeration and structure of trapezoidal words

DOI10.1016/J.TCS.2012.11.007MaRDI QIDQ1935783zbMATH OpenOpenAlexFDO

Authors Michelangelo Bucci, Alessandro De Luca, Gabriele Fici

Publication date 19 February 2013

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1203.1203

zbMATH Keywords

closed wordsenumerative formulapalindromesrich wordsspecial factorsSturmian wordstrapezoidal words

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Abstract: Trapezoidal words are words having at most $n+1$ distinct factors of length $n$ for every $nge0$. 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.

Recommendations

• A classification of trapezoidal words
• Characteristic parameters and special trapezoidal words
• Rich, Sturmian, and trapezoidal words
• A combinatorial problem on trapezoidal words.
• Generalized trapezoidal words

Cited in

(18)

• A combinatorial problem on trapezoidal words.
• Closed Ziv-Lempel factorization of the \(m\)-bonacci words
• Characteristic parameters and special trapezoidal words
• The sequence of open and closed prefixes of a Sturmian word
• Open and closed factors in Arnoux-Rauzy words
• Closed, palindromic, rich, privileged, trapezoidal, and balanced words in automatic sequences
• On the structure of bispecial Sturmian words
• A classification of trapezoidal words
• Initial non-repetitive complexity of infinite words
• Generalized trapezoidal words
• Maximal closed substrings
• Asymptotic bounds for the number of closed and privileged words
• Some results on digital segments and balanced words
• A symmetry property of Christoffel words
• A symmetry property of Christoffel words
• On palindromic periodicities
• Efficient algorithms to compute closed substrings
• Rich, Sturmian, and trapezoidal words

This page was built for publication: Enumeration and structure of trapezoidal words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1935783)