Journal of Integer Sequences, Vol. 16 (2013), Article 12.1.5

On Additive Complexity of Infinite Words


Graham Banero
Department of Mathematics
Simon Fraser University
8888 University Drive
Burnaby, BC V5A 1S6
Canada

Abstract:

We consider questions related to the structure of infinite words (over an integer alphabet) with bounded additive complexity, i.e., words with the property that the number of distinct sums exhibited by factors of the same length is bounded by a constant that depends only on the word. We describe how bounded additive complexity impacts the slope of the word and how a non-erasing morphism may affect the boundedness of a given words additive complexity. We prove the existence of recurrent words with constant additive complexity equal to any given odd positive integer. In the last section, we discuss a generalization of additive complexity. Our results suggest that words with bounded additive complexity may be viewed as a generalization of balanced words.


Full version:  pdf,    dvi,    ps,    latex    


Received September 17 2012; revised version received January 6 2013. Published in Journal of Integer Sequences, January 7 2013.


Return to Journal of Integer Sequences home page