A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Enumeration and structure of trapezoidal words
Tekijät: Michelangelo Bucci, Alessandro De Luca, Gabriele Fici
Kustantaja: ELSEVIER SCIENCE BV
Kustannuspaikka: AMSTERDAM; PO BOX 211, 1000 AE AMSTERDAM, NETHERLANDS
Julkaisuvuosi: 2013
Journal: Theoretical Computer Science
Tietokannassa oleva lehden nimi: Theoretical Computer Science
Lehden akronyymi: Theor.Comput.Sci.
Vuosikerta: 468
Aloitussivu: 12
Lopetussivu: 22
Sivujen määrä: 11
ISSN: 0304-3975
DOI: https://doi.org/10.1016/j.tcs.2012.11.007
Tiivistelmä
Trapezoidal words are words having at most n + 1 distinct factors of length n for every n >= 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, 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. (C) 2012 Elsevier B.V. All rights reserved.
Trapezoidal words are words having at most n + 1 distinct factors of length n for every n >= 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, 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. (C) 2012 Elsevier B.V. All rights reserved.
Turun yliopiston Tutkimustietojärjestelmän portaali