Book contents
- Frontmatter
- Contents
- Preface
- Permissions
- 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
- Bibliography
- Index
8 - First-order formulas for fundamental sequence properties
Published online by Cambridge University Press: 09 September 2022
Book contents
- Frontmatter
- Contents
- Preface
- Permissions
- 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
- Bibliography
- Index
Summary
In this chapter we will examine about 80 different fundamental properties of automatic sequences, and show how each one can be encoded by first-order logical formulas. We then use Walnut to re-derive new proofs of known results, or prove new results, concerning some famous automatic sequences. You can use these examples to learn what Walnut is capable of, but also as a ‘catalogue’ of first-order statements of fundamental properties of sequences.
- Type
- Chapter
- Information
- The Logical Approach to Automatic SequencesExploring Combinatorics on Words with Walnut, pp. 113 - 192Publisher: Cambridge University PressPrint publication year: 2022