| Combinatorics on words is a fairly new field of mathematics, branching from combi-natorics, which focuses on the study of words and formal languages. The subject studies theletters (or symbols) and the sequences they form, and sheds light on various other areas ofmathematics, such as algebra, symbolic dynamic and computer science.The history of combinatorics on words date back to the beginning of the last century,when A. Thue started to work on repetition-free words. He proved, among other things,the existence of an infinite square-free word over a ternary alphabet. A word is a sequenceof symbols, finite of infinite, taken from a finite alphabet. Consequently, words can beseen as discrete combinatorial objects or discrete algebraic objects in a noncommutativestructure. These two facts–discreteness and noncommutativity-are the two fundamentalfeatures of words, and explain why many problems are so difficult. Words are central objectsof automata theory. In the standard model of computing, when computing on numberscomputers operate on words, i.e., representations of numbers as words. Sturmian wordsplay an important role in combinatorics on words and they share a number of extremalproperties.The thesis is organized as follows: in the introductory chapter we introduce the back-ground of combinatorics on words, review and make brief remarks on the pioneer’s work.An introduction to the fundamental knowledge of combinatorics on words is presented inchapter2. In the following chapter, we provide the proofs of several essential lemmas andtheorems which will be used in the thesis, such as critical factorization theorem and theperiodicity of standard words. In the next chapter we prove that, denoting p_x(n) the localperiod of an infinite word x at point n, we prove that x is a characteristic Sturmian wordif and only if p_x(n)≤n+1for all n≥1and equal n+1for infinitely many integers n.As a byproduct we give the exact formula for the number of critical points for every finitestandard Sturmian word. |
PDF Full Text Request