Formal Languages, Automata and Numeration Systems Volume 2

<p>FOREWORD ix</p>
<p>INTRODUCTION xiii</p>
<p>CHAPTER 1. CRASH COURSE ON REGULAR LANGUAGES 1</p>
<p>1.1. Automata and regular languages 2</p>
<p>1.2. Adjacency matrix 14</p>
<p>1.3. Multidimensional alphabet 17</p>
<p>1.4. Two pumping lemmas 19</p>
<p>1.5. The minimal automaton 23</p>
<p>1.6. Some operations preserving regularity 29</p>
<p>1.7. Links with automatic sequences and recognizable sets 32</p>
<p>1.8. Polynomial regular languages 37</p>
<p>1.8.1. Tiered words 40</p>
<p>1.8.2. Characterization of regular languages of polynomial growth 43</p>
<p>1.8.3. Growing letters in morphic words 49</p>
<p>1.9. Bibliographic notes and comments 51</p>
<p>CHAPTER 2. A RANGE OF NUMERATION SYSTEMS 55</p>
<p>2.1. Substitutive systems 58</p>
<p>2.2. Abstract numeration systems 67</p>
<p>2.2.1. Generalization of Cobham s theorem on automatic sequences 74</p>
<p>2.2.2. Some properties of abstract numeration systems 86</p>
<p>2.3. Positional numeration systems 89</p>
<p>2.4. Pisot numeration systems 98</p>
<p>2.5. Back to –expansions 107</p>
<p>2.5.1. Representation of real numbers 107</p>
<p>2.5.2. Link between representations of integers and real numbers 112</p>
<p>2.5.3. Ito Sadahiro negative base systems 114</p>
<p>2.6. Miscellaneous systems 117</p>
<p>2.7. Bibliographical notes and comments 123</p>
<p>CHAPTER 3. LOGICAL FRAMEWORK AND DECIDABILITY ISSUES 129</p>
<p>3.1. A glimpse at mathematical logic 132</p>
<p>3.1.1. Syntax 132</p>
<p>3.1.2. Semantics 136</p>
<p>3.2. Decision problems and decidability 140</p>
<p>3.3. Quantifier elimination in Presburger arithmetic 143</p>
<p>3.3.1. Equivalent structures 143</p>
<p>3.3.2. Presburger s theorem and quantifier elimination 146</p>
<p>3.3.3. Some consequences of Presburger s theorem 150</p>
<p>3.4. B&uuml;chi s theorem 156</p>
<p>3.4.1. Definable sets 157</p>
<p>3.4.2. A constructive proof of B&uuml;chi s theorem 159</p>
<p>3.4.3. Extension to Pisot numeration systems 168</p>
<p>3.5. Some applications 170</p>
<p>3.5.1. Properties about automatic sequences 170</p>
<p>3.5.2. Overlap–freeness&nbsp; 172</p>
<p>3.5.3. Abelian unbordered factors 173</p>
<p>3.5.4. Periodicity 177</p>
<p>3.5.5. Factors 178</p>
<p>3.5.6. Applications to Pisot numeration systems 180</p>
<p>3.6. Bibliographic notes and comments 183</p>
<p>CHAPTER 4. LIST OF SEQUENCES 187</p>
<p>BIBLIOGRAPHY 193</p>
<p>INDEX 231</p>
<p>SUMMARY OF VOLUME 1 235</p>