Counting Minimal Semi-Sturmian Words
- UNCG Author/Contributor (non-UNCG co-authors, if there are any, appear on document)
- Francine Blanchet-Sadri, Professor (Creator)
- Institution
- The University of North Carolina at Greensboro (UNCG )
- Web Site: http://library.uncg.edu/
Abstract: A finite Sturmian word w is a balanced word over the binary alphabet {a,b}, that is, for all subwords u andv of w of equal length, ||u|a-|v|a|=1, where |u|a and |v|a denote the number of occurrences of the lettera in u and v, respectively. There are several other characterizations, some leading to efficient algorithms for testing whether a finite word is Sturmian. These algorithms find important applications in areas such as pattern recognition, image processing, and computer graphics. Recently, Blanchet-Sadri and Lensmire considered finite semi-Sturmian words of minimal length and provided an algorithm for generating all of them using techniques from graph theory. In this paper, we exploit their approach in order to count the number of minimal semi-Sturmian words. We also present some other results that come from applying this graph theoretical framework to subword complexity.
Counting Minimal Semi-Sturmian Words
PDF (Portable Document Format)
580 KB
Created on 6/30/2014
Views: 1884
Additional Information
- Publication
- Discrete Applied Mathematics, 161(18), 2851-2861
- Language: English
- Date: 2013
- Keywords
- Combinatorics on words, Graph theory, Subword complexity, Semi-Sturmian words, Euler’s totient function