|
|
Jeffrey Shallit |
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)
[Walnut] is an elegant and powerful tool that can be used with great effect in the analysis of morphic sequences...
We encourage the reader to check out the new and highly entertaining textbook for many more examples of the power of Walnut.
Robbert Fokkink, Gerard Francis Ortega, and Dan Rust,
Corner The Empress,
Arxiv preprint, 2022.
Here's a review by William Gasarch at U. Maryland; it appeared in SIACT News 55 (3) (September 2024), 6-10.
Here's a review in Zentralbatt by Štěpán Holub.
Page 55: Line 10, replace F with Fi. (Lucas Mol)
Page 59: In the algorithm Semigroup Trick, the line τ(s) = tw should read τ(s) = sw. (Pierre Popoli)
Page 85: In the statement of Theorem 6.3.2, the "P" in the last sentence should be \varphi;. (Jonathan Allin)
Page 109: Exercise 41, section 7.11: Part (c), second term should be F_3, not F_4. (Robbert Fokkink).
Page 119: Section 8.1.9: the Walnut code for "rsrun0" is wrong; it should be
def rsrun0 "n>=1 & (At t<n => RS[i+t]=@0) & RS[i+n]!=@0 & (i=0|RS[i-1]!=@0)":
Page 125: Line 4, delete the word "corresponding". (Lucas Mol)
Page 136: Not exactly a corrigendum---more of an addendum. Part of Theorem 8.5.4 can be found in T. Downarowicz, Reading along arithmetic progressions, Colloq. Math. 80 (1999), 293-296.
Page 156: In line 11, replace "0 except y" with "except y". In line 18, replace "0,3,4,5,9" with "3,4,5,7,9". (Manon Stipulanti)
Page 166: In the definition of tmbord, the letter m should be replaced by j.
Page 167: The definition of fibbord has an unnecessary
variable t. It should read
def fibbord "?msd_fib m>=1 & m<n & $ffactoreq(i,(i+n)-m,m)":
(Manon Stipulanti)
Page 174:
The definition of tmbord has an unnecessary
variable t. It should read
def tmbord "m>=1 & m<n & $tmfactoreq(i,(i+n)-m,m)":
(Manon Stipulanti)
The definition of pfbord has an unnecessary
variable t. It should read
def pfbord "m>=1 & m<n & $pffactoreq(i,(i+n)-m,m)":
(Manon Stipulanti)
Page 233: Open Question 9.11.9 has now been solved, by the preprint at https://arxiv.org/abs/2301.11473.