<abstract xmlns="http://www.w3.org/1999/xhtml"> A sequence (an)n≥0 is k-automatic if there is a finite automaton that, on input n expressed in base k, reaches a state with output an. In this paper I will survey some recent advances concerning enumeration of various aspects of these sequences, such as the recurrence function, and the subword complexity (which counts the number of distinct blocks of length n). </abstract>

A sequence (an)n≥0 is k-automatic if there is a finite automaton that, on input n expressed in base k, reaches a state with output an. In this paper I will survey some recent advances concerning enumeration of various aspects of these sequences, such as the recurrence function, and the subword complexity (which counts the number of distinct blocks of length n).

Enumeration and Automatic Sequences

School of Computer Science University of Waterloo Canada

Pure Mathematics and Applications

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

{"article-title":"Enumeration and Automatic Sequences"}

A sequence (an)n≥0 is k-automatic if there is a finite automaton that, on input n expressed in base k, reaches a state with output an. In this paper I will...

Enumeration and Automatic Sequences

Publié en ligne: 07 oct. 2015

Pages: 96 - 106

Reçu: 10 juil. 2014

DOI: https://doi.org/10.1515/puma-2015-0008

Mots clés
enumeration, automatic sequence, recurrence, regular sequence, automaton, bordered word, synchronized sequence, predicate, logic, Fibonacci representation

© 2015

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Enumeration and Automatic Sequences

Publié en ligne: 07 oct. 2015

Pages: 96 - 106

Reçu: 10 juil. 2014

DOI: https://doi.org/10.1515/puma-2015-0008

Mots clésenumeration, automatic sequence, recurrence, regular sequence, automaton, bordered word, synchronized sequence, predicate, logic, Fibonacci representation

© 2015

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Mots clés
enumeration, automatic sequence, recurrence, regular sequence, automaton, bordered word, synchronized sequence, predicate, logic, Fibonacci representation