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
6 - First-order logic and automatic sequences
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 give yet another fundamental way to think about automatic sequences, based on first-order logic. This revolutionary approach is originally due to Büuchi, with elaborations and additions by Bruyére, Hansel, Michaux, and Villemaire, and their ideas form the basis for this book. A good reference for the material in this section is the wonderful survey paper by these last four authors [56].
- Type
- Chapter
- Information
- The Logical Approach to Automatic SequencesExploring Combinatorics on Words with Walnut, pp. 82 - 95Publisher: Cambridge University PressPrint publication year: 2022