Journal of Integer Sequences, Vol. 6 (2003), Article 03.3.8

A Criterion for Non-Automaticity of Sequences

Jan-Christoph Schlage-Puchta
Mathematisches Institut
Eckerstr. 1
79111 Freiburg

Abstract: We give a criterion for a sequence (a_n)_{n >= 1} to be non-automatic, i.e., for when there does not exist a finite automaton generating this sequence. As application we generalize a result of Yazdani on the non-automaticity of multiplicative sequences.

Full version:  pdf,    dvi,    ps,    latex.    

Received February 6, 2003; revised version received November 10, 2003. Published in Journal of Integer Sequences November 16, 2003.

Return to Journal of Integer Sequences home page