<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

Published Online: Oct 07, 2015

Page range: 96 - 106

Received: Jul 10, 2014

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

Keywords
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

Published Online: Oct 07, 2015

Page range: 96 - 106

Received: Jul 10, 2014

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

Keywordsenumeration, 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.

Keywords
enumeration, automatic sequence, recurrence, regular sequence, automaton, bordered word, synchronized sequence, predicate, logic, Fibonacci representation