《特征Sturmian词的性质论文》由会员分享，可在线阅读，更多相关《特征Sturmian词的性质论文（29页珍藏版）》请在金锄头文库上搜索。
1、.A Thesis Submitted in Partial Fulllment of the Requirementsfor the Degree of Master of ScienceProperties of characteristic Sturmian WordsCandidate : WU FengtianMajor : Pure MathematicsSupervisor : Professor TAN BoHuazhong University of Science & TechnologyWuhan 430074, P. R. ChinaMay, 201329 / 29.独
2、创性声明本人声明所呈交的学位论文是我个人在导师的指导下进行的研究工作及取得的研究成果。尽我所知,除文中已标明引用的内容外,本论文不包含任何其他人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体,均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。学位论文作者签名：.日期：年月日.学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定,即：学校有权保留并向国家有关部门或机构送交论文的复印件和电子版,允许论文被查阅和借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检索,可以采用影印、缩印或扫描等复制手段保存和汇编本
3、学位论文。.本论文属于保密 ,在不保密。年解密后适用本授权书。.请在以上方框内打 .学位论文作者签名：指导教师签名：.日期：年月日日期：年月日.华 中 科技大学硕士学位论文.摘要.词的组合是由几个数学分支产生的, 也是一个比较新的数学领域. 它主要研究词和形式语言, 研究字符或符号以及由其生成的序列. 词的组合影响了数学研究中的各个领域, 包括代数学、符号动力系统、及计算机理论科学, 并且在这些领域中做出了广泛的贡献.词的组合的历史可以追溯到二十世纪初, Axel Thue 是第一个系统地研究词的问题的数学家, 他证明了在三元字符集上存在无平方无限词. 词就是定义在有限的字符集上的有限或无限的
4、符号序列, 因此, 可以将词当做离散的组合对象或非交换结构下离散的代数对象. 以上就是词的两个基本特征: 离散性和不可交换性, 这也在一定程度上说明了词的问题的难度. 词是自动机理论的核心研究对象, 在标准化计算中任何的数值计算实质上都是词上的运算. Sturmian 词是十分重要的一类词, 并且 Sturmian 词具有一系列的临界性质.本文绪论部分, 介绍了词的组合的研究背景, 简要地总结了已经得到的研究结果.第二章介绍了相关的基础知识, 包括有限词, 无限词以及 Sturmian 词, 标准词 Sturmian词与特征 Sturmian 词. 第三章给出了文中涉及到的一些结论与定理的证明
5、, 特别是与本文结果相关的临界因子分解定理及标准词的周期性. 最后一章证明了:一个无穷词.x 是一个特征 Sturmian 词当且仅当对所有的 n1 , pxn + 1 且对无限多个整.数 n 有 px = n + 1, 这里px 表示x 在n 处的局部周期. 并给出了计算有限标准Sturmian 词中临界点个数的公式.关键词： 临界点, 临界因子分解定理, 周期性, 特征 Sturmian 词I.华 中 科技大学硕士学位论文.AbstractCombinatorics on words is a fairly new eld of mathematics, branching from co
6、mbi-natorics, which focuses on the study of words and formal languages. The subject studies theletters 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 begi
7、nning of the last century,when A. Thue started to work on repetition-free words. He proved, among other things,the existence of an innite square-free word over a ternary alphabet. A word is a sequenceof symbols, nite of innite, taken from a nite alphabet. Consequently, words can beseen as discrete c
8、ombinatorial 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 difcult. Words are central objectsof automata theory. In the standard model of computing
9、, 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
10、of combinatorics on words, review and make brief remarks on the pioneers work.An introduction to the fundamental knowledge of combinatorics on words is presented inchapter 2. In the following chapter, we provide the proofs of several essential lemmas andtheorems which will be used in the thesis, suc
11、h as critical factorization theorem and theperiodicity of standard words. In the next chapter we prove that, denoting px the localperiod of an innite word x at point n, we prove that x is a characteristic Sturmian wordif and only if px n + 1 for all n 1 and equal n + 1 for innitely many integers n.A
12、s a byproduct we give the exact formula for the number of critical points for every nitestandard Sturmian word.Keywords: Critical point, Critical Factorization Theorem, Peroidicity, Sturmian wordsII.华 中 科技大学硕士学位论文.目录.摘要 .I.Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13、. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1 绪论1.1 问题研究的背景 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.2 研究现状 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14、 . . . . . . . . . . . . . . . . .1.3 本文的结构安排 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .II.2 预备知识2.1 有限词. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15、 . . . . 2.2 无限词. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 标准 Sturmian 词与特征 Sturmian 词. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 定理的证明.3.1Fine-Wilf 定理 . . . . . . . . . . . . . . . . . . . . . . . . .
