Computer Science – Formal Languages and Automata Theory
Scientific paper
2011-08-18
EPTCS 63, 2011, pp. 129-137
Computer Science
Formal Languages and Automata Theory
In Proceedings WORDS 2011, arXiv:1108.3412
Scientific paper
10.4204/EPTCS.63.18
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.
No associations
LandOfFree
A Classification of Trapezoidal Words does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A Classification of Trapezoidal Words, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Classification of Trapezoidal Words will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-180614