The Logical Approach to Automatic Sequences

Exploring Combinatorics on Words with Walnut

AvJeffrey Shallit

Häftad, Engelska, 2022

Del 482 i serien London Mathematical Society Lecture Note Series

968 kr

Beställningsvara. Skickas inom 7-10 vardagar. Fri frakt över 249 kr.

Beskrivning

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.

Produktinformation

Utgivningsdatum:2022-09-29
Mått:151 x 230 x 20 mm
Vikt:540 g
Format:Häftad
Språk:Engelska
Serie:London Mathematical Society Lecture Note Series
Antal sidor:374
Förlag:Cambridge University Press
ISBN:9781108745246

Utforska kategorier

Talteori inom Naturvetenskap och teknik
Systemvetenskap och AI inom Data och IT
Matematikens grunder inom Naturvetenskap och teknik

Mer om författaren

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.

Recensioner i media

'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

Innehållsförteckning

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.