The interplay between words, computability, algebra and arithmetic has now proved its relevance and fruitfulness. Indeed, the cross-fertilization between formal logic and finite automata (such as that initiated by J.R. Büchi) or between combinatorics on words and number theory has paved the way to recent dramatic developments, for example, the transcendence results for the real numbers having a "simple" binary expansion, by B. Adamczewski and Y. Bugeaud.This book is at the heart of this interplay through a unified exposition. Objects are considered with a perspective that comes both from theoretical computer science and mathematics. Theoretical computer science offers here topics such as decision problems and recognizability issues, whereas mathematics offers concepts such as discrete dynamical systems.The main goal is to give a quick access, for students and researchers in mathematics or computer science, to actual research topics at the intersection between automata and formal language theory, number theory and combinatorics on words.The second of two volumes on this subject, this book covers regular languages, numeration systems, formal methods applied to decidability issues about infinite words and sets of numbers.

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 polynomialgrowth 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 automaticsequences 742.2.2. Some properties of abstract numeration systems 862.3. Positional numeration systems 892.4. Pisot numeration systems 982.5. Back to beta-expansions 1072.5.1. Representation of real numbers 1072.5.2. Link between representations of integers and real numbers1122.5.3. Ito-Sadahiro negative base systems 1142.6. Miscellaneous systems 1172.7. Bibliographical notes and comments 123CHAPTER 3. LOGICAL FRAMEWORK AND DECIDABILITY ISSUES1293.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 elimination1463.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 theorem1593.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