The Logical Approach to Automatic Sequences
Exploring Combinatorics on Words with Walnut

Learn how to automatically prove mathematical statements in combinatorics, sequences, and number theory.

Jeffrey Shallit (Author)

9781108745246, Cambridge University Press

Paperback / softback, published 29 September 2022

374 pages
23 x 15.1 x 2 cm, 0.54 kg

'This is a marvelous book with a very fresh approach to the decidability and structural analysis of combinatorics on words. It combines three different mathematical research topics: first-order logic, automatic sequences, and combinatorics on words. More precisely, it interprets infinite morphic words as automatic sequences via k-automata and expresses properties (of words) in first-order logic. Due to the decidability of such logic, decision results and structural properties of combinatorics on words are established. A crucial role in this approach is to employ a powerful software package called Walnut. The author illustrates the power of his approach by giving a huge number of results obtained by this method. Not only are old and new results proved, but even some errors in previous ones are corrected. Anybody interested in, or curious about, this topic should be enthusiastic about this masterpiece.' Juhani Karhumäki, University of Turku (Emeritus)

Automatic sequences are sequences over a finite alphabet generated by a finite-state machine. This book presents a novel viewpoint on automatic sequences, and more generally on combinatorics on words, by introducing a decision method through which many new results in combinatorics and number theory can be automatically proved or disproved with little or no human intervention. This approach to proving theorems is extremely powerful, allowing long and error-prone case-based arguments to be replaced by simple computations. Readers will learn how to phrase their desired results in first-order logic, using free software to automate the computation process. Results that normally require multipage proofs can emerge in milliseconds, allowing users to engage with mathematical questions that would otherwise be difficult to solve. With more than 150 exercises included, this text is an ideal resource for researchers, graduate students, and advanced undergraduates studying combinatorics, sequences, and number theory.

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.

Subject Areas: Maths for computer scientists [UYAM], Combinatorics & graph theory [PBV], Number theory [PBH], Mathematical logic [PBCD]