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.
Learn how to automatically prove mathematical statements in combinatorics, sequences, and number theory.
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.
'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
'This book focuses on a decision procedure, which is rather easy to
implement as a computer program and allows one to prove many
results, classical and new, in combinatorics on words. It addresses
decision problems and enumeration problems on sequences that are
expressible in first-order logic. The reader will appreciate the
style, which is relaxed and pleasant to read, and the numerous
examples and exercises. This book is a useful complement to the
previous monograph, Automatic Sequences, co-authored by Shallit and
Allouche.' Yann Bugeaud, University of Strasbourg
'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)
'You should buy this book for the following reasons. 1. For your
own enlightenment. 2. For examples of concepts you can teach in a
course in automata theory. That is, even if you do not plan to use
or teach Walnut, there is much of interest in the book.' William
Gasarch, SIGACT News
|
Ask a Question About this Product More... |
|
