Muutke küpsiste eelistusi

Logical Approach to Automatic Sequences: Exploring Combinatorics on Words with Walnut [Pehme köide]

4.00/5 (2 hinnangut Goodreads-ist)
(University of Waterloo, Ontario)
  • Formaat: Paperback / softback, 374 pages, kõrgus x laius x paksus: 230x151x20 mm, kaal: 540 g, Worked examples or Exercises
  • Sari: London Mathematical Society Lecture Note Series
  • Ilmumisaeg: 29-Sep-2022
  • Kirjastus: Cambridge University Press
  • ISBN-10: 1108745245
  • ISBN-13: 9781108745246
Teised raamatud teemal:
Logical Approach to Automatic Sequences: Exploring Combinatorics on Words with WalnutSuurem pilt
  • Formaat: Paperback / softback, 374 pages, kõrgus x laius x paksus: 230x151x20 mm, kaal: 540 g, Worked examples or Exercises
  • Sari: London Mathematical Society Lecture Note Series
  • Ilmumisaeg: 29-Sep-2022
  • Kirjastus: Cambridge University Press
  • ISBN-10: 1108745245
  • ISBN-13: 9781108745246
Teised raamatud teemal:
Püsilink: https://www.kriso.ee/db/9781108745246.html
Märksõnad:
Readers will learn how to automatically prove or disprove new results in combinatorics and number theory in milliseconds by phrasing their desired results in first-order logic and using free software to automate the computation process. Containing more than 150 exercises, this text is an ideal resource for students and researchers.

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.

Arvustused

'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

Muu info

Learn how to automatically prove mathematical statements in combinatorics, sequences, and number theory.
Preface xi
Permissions xiv
1 Introduction
1(9)
1.1 Powers, factors, periods, exponents
2(3)
1.2 A decision procedure
5(1)
1.3 Two simple examples
6(4)
2 Words and sequences
10(22)
2.1 Finite words
10(6)
2.2 Infinite words (sequences)
16(2)
2.3 Morphisms and morphic words
18(1)
2.4 Some famous sequences
18(10)
2.5 Properties of sequences
28(2)
2.6 Proving properties of words through exhaustive search
30(1)
2.7 Languages
31(1)
3 Number representations and numeration systems
32(15)
3.1 Base-k representation
32(1)
3.2 Fibonacci representation
33(1)
3.3 Tribonacci representation
34(1)
3.4 Pell representation
35(1)
3.5 Ostrowski representation
36(11)
4 Automata
47(15)
4.1 Basics of automata
47(2)
4.2 Nondeterminism
49(1)
4.3 Regular expressions
49(1)
4.4 Operations on automata
50(2)
4.5 Minimization
52(1)
4.6 Automata with output
53(1)
4.7 Automata with multiple inputs
54(1)
4.8 Combining multiple DFAs into a DFAO
54(1)
4.9 Enumeration of paths in a DFA
55(2)
4.10 Formal series and linear representations
57(1)
4.11 The semigroup trick
58(2)
4.12 Transducers
60(2)
5 Automatic sequences
62(20)
5.1 Definitions and examples
62(2)
5.2 DFAOs for other famous sequences
64(1)
5.3 Automatic sets
65(1)
5.4 Cobham's little theorem
65(3)
5.5 The k-kernel
68(3)
5.6 Using the k-kernel to guess a DFAO for a sequence
71(4)
5.7 Another way to guess the automaton
75(1)
5.8 Cobham's big theorem
76(1)
5.9 Fibonacci-automatic sequences
77(1)
5.10 Tribonacci-automatic sequences
78(1)
5.11 Pell-automatic sequences
79(1)
5.12 Ostrowski-automatic sequences
79(1)
5.13 Two-dimensional sequences
80(2)
6 First-order logic and automatic sequences
82(14)
6.1 First-order logic
82(1)
6.2 Presburger arithmetic
83(2)
6.3 Decidability of Presburger arithmetic
85(2)
6.4 Extending Presburger arithmetic
87(2)
6.5 Useful formulas
89(1)
6.6 More about logic
90(3)
6.7 Other kinds of automatic sequences
93(1)
6.8 Consequences
94(1)
6.9 Limitations
95(1)
7 Using walnut
96(17)
7.1 Syntax of walnut
97(3)
7.2 Regular expressions
100(1)
7.3 DFAOs included with walnut
101(1)
7.4 Creating DFAOs and moronisms
102(2)
7.5 Invoking Walnut
104(1)
7.6 Output of a walnut command
104(1)
7.7 Denning your own DFAs and DFAOs
105(1)
7.8 Combining two different numeration systems
106(1)
7.9 The correctness issue
107(1)
7.10 Some basic formulas in Walnut
108(1)
7.11 Proving summation identities with Walnut
109(1)
7.12 Custom numeration systems
109(1)
7.13 Tips for using walnut
110(1)
7.14 What to do if a query runs out of space
111(2)
8 First-order formulas for fundamental sequence properties
113(80)
8.1 Symbol and word occurrences
114(9)
8.2 Representation of integers
123(1)
8.3 Properties of automatic sets
124(1)
8.4 Periodicity, quasiperiodicity, and pseudoperiodicity
125(5)
8.5 Squares, cubes, and other powers
130(26)
8.6 Conjugates, palindromes, and borders
156(12)
8.7 Recurrence, uniform recurrence, linear recurrence
168(2)
8.8 Types of words
170(12)
8.9 Comparing two or more sequences
182(2)
8.10 Two-dimensional arrays
184(2)
8.11 Other topics
186(5)
8.12 What properties of factors can walnut check?
191(2)
9 Regular sequences and enumeration problems
193(44)
9.1 Two characterizations of k-regular sequences
193(3)
9.2 Examples of k-regular sequences
196(2)
9.3 Converting between two representations
198(3)
9.4 Basic properties of k-regular sequences
201(3)
9.5 Non-closure of the class of regular sequences
204(1)
9.6 K-regular sequences and k-automatic sequences
205(2)
9.7 Growth rate of k-regular sequences
207(1)
9.8 Principles of enumeration
207(7)
9.9 Asymptotic behavior of k-regular sequences
214(2)
9.10 Average values of regular sequences
216(2)
9.11 Enumeration examples
218(18)
9.12 How to guess the relations for a k-regular sequence
236(1)
10 Synchronized sequences
237(66)
10.1 Automata computing relations
237(1)
10.2 K-synchronized sequences
238(3)
10.3 Closure properties of synchronized sequences
241(2)
10.4 Automatic, synchronized, and regular sequences
243(2)
10.5 An example: the appearance function
245(2)
10.6 Growth rate of synchronized sequences
247(4)
10.7 Efficient computation of synchronized sequences
251(1)
10.8 Examples of synchronized functions
252(23)
10.9 First-order properties of synchronized sequences
275(1)
10.10 Synchronized sequences in two bases
276(1)
10.11 Fibonacci synchronization
277(9)
10.12 Tribonacci-synchronized sequences
286(1)
10.13 Abelian properties
287(11)
10.14 Unsynchronized sequences
298(2)
10.15 How to guess a synchronized sequence
300(3)
11 Additive number theory
303(13)
11.1 The evil and odious numbers
304(2)
11.2 Other examples
306(2)
11.3 Summands from different sets
308(1)
11.4 Wythoff sequences
308(2)
11.5 The method of over- and under-approximation
310(1)
11.6 De Bruijn's problem
311(1)
11.7 Frobenius numbers
311(3)
11.8 Counting number of representations
314(2)
12 Paperfolding sequences
316(11)
12.1 The general idea
316(3)
12.2 Appearance
319(1)
12.3 Powers in the paperfolding sequence
320(3)
12.4 Palindromes
323(1)
12.5 Subword complexity
323(2)
12.6 Rampersad's conjecture
325(2)
13 A final word
327(3)
13.1 Limits to the approach
327(3)
References 330(20)
Index 350
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.