<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

Pubblicato online: 07 ott 2015

Pagine: 96 - 106

Ricevuto: 10 lug 2014

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

Parole chiave
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

Pubblicato online: 07 ott 2015

Pagine: 96 - 106

Ricevuto: 10 lug 2014

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

Parole chiaveenumeration, 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.

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