Formal Languages, Automata and Numeration Systems 2

Michel Rigo is Professor at the Department of Mathematics at the University of Liège, Belgium.

• Foreword ixIntroduction XIIIChapter 1. Crash Course On Regular Languages 11.1 Automata and regular languages 21.2 Adjacency matrix 141.3 Multidimensional alphabet 171.4 Two pumping lemmas 191.5 The minimal automaton 231.6 Some operations preserving regularity 291.7 Links with automatic sequences and recognizable sets 321.8 Polynomial regular languages 371.8.1 Tiered words 401.8.2 Characterization of regular languages of polynomial growth 431.8.3 Growing letters in morphic words 491.9 Bibliographic notes and comments 51Chapter 2. A Range Of Numeration Systems 552.1 Substitutive systems 582.2 Abstract numeration systems 672.2.1 Generalization of Cobham’s theorem on automatic sequences 742.2.2 Some properties of abstract numeration systems 862.3 Positional numeration systems 892.4 Pisot numeration systems 982.5 Back to β-expansions 1072.5.1 Representation of real numbers 1072.5.2 Link between representations of integers and real numbers 1122.5.3 Ito–Sadahiro negative base systems 1142.6 Miscellaneous systems 1172.7 Bibliographical notes and comments 123Chapter 3. Logical Framework and Decidability Issues 1293.1 A glimpse at mathematical logic 1323.1.1 Syntax 1323.1.2 Semantics 1363.2 Decision problems and decidability 1403.3 Quantifier elimination in Presburger arithmetic 1433.3.1 Equivalent structures 1433.3.2 Presburger’s theorem and quantifier elimination 1463.3.3 Some consequences of Presburger’s theorem 1503.4 Büchi’s theorem 1563.4.1 Definable sets 1573.4.2 A constructive proof of Büchi’s theorem 1593.4.3 Extension to Pisot numeration systems 1683.5 Some applications 1703.5.1 Properties about automatic sequences 1703.5.2 Overlap-freeness 1723.5.3 Abelian unbordered factors 1733.5.4 Periodicity 1773.5.5 Factors 1783.5.6 Applications to Pisot numeration systems 1803.6 Bibliographic notes and comments 183Chapter 4 List Of Sequences 187Bibliography 193Index 231Summary of Volume 1 235

"This book follows Formal Languages, Automata and Numeration Systems. Vol. 1. Introduction to Combinatorics on Words. It contains essentially two parts that are quite interesting." (Zentralblatt MATH 2016)