The Logical Approach to Automatic Sequences

Jeffrey Shallit is Professor of Computer Science in the Faculty of Mathematics at the University of Waterloo. His research areas include formal languages, finite automata, combinatorics on words, algorithmic number theory, algebra, and the history of mathematics. He has published approximately 300 articles on these topics since 1975. He is also the author or co-author of four books. He is a foreign member of the Finnish Academy of Science and Letters.

• 1. Introduction; 2. Words and sequences; 3. Number representations and numeration systems; 4. Automata; 5. Automatic sequences; 6. First-order logic and automatic sequences; 7. Using Walnut; 8. First-order formulas for fundamental sequence properties; 9. Regular sequences and enumeration problems; 10. Synchronized sequences; 11. Additive number theory; 12. Paperfolding sequences; 13. A final word; References; Index.

'In this book, Jeffrey Shallit gives combinatorics on words enthusiasts access to new and exciting tools to compute examples and test conjectures. Far from a mere user's manual, the text fully introduces the reader to the interactions of logic and words, proving basic theorems like the decidability of Presburger's arithmetic. It will be of great use to students and researchers, as well as the source of many future developments.' Dominique Perrin, Université Gustave Eiffel