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