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
9 - Regular sequences and enumeration problems
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
Although the automatic sequences form a large and interesting class, one drawback is that they need to take their values in a finite set. But many interesting sequences, such as (s2(n))n.0 (counting the sum of the bits in the base-2 representation of n), take their values in N (or Z, or any semiring). We would like to find a generalization that allows this.
- Type
- Chapter
- Information
- The Logical Approach to Automatic SequencesExploring Combinatorics on Words with Walnut, pp. 193 - 236Publisher: Cambridge University PressPrint publication year: 2022