On additive complexity of infinite words

MaRDI QIDQ5404275zbMATH OpenFDO

Authors Graham Banero

Publication date 24 March 2014

Full work available at URL https://arxiv.org/abs/1209.4691, http://www.emis.de/journals/JIS/VOL16/Banero/banero3.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

combinatorics on wordssubword complexityadditive square

Mathematics Subject Classification ID

Combinatorics on words (68R15) Ramsey theory (05D10)

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 word's 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.

Recommendations

• On abelian and additive complexity in infinite words
• Sturmian words and constant additive complexity
• Approximations of additive squares in infinite words
• scientific article; zbMATH DE number 2123422
• Ultimately constant abelian complexity of infinite words

Cited in

(9)

• scientific article; zbMATH DE number 2123422 (Why is no real title available?)
• Approximations of additive squares in infinite words
• On abelian and additive complexity in infinite words
• scientific article; zbMATH DE number 4057009 (Why is no real title available?)
• scientific article; zbMATH DE number 1834659 (Why is no real title available?)
• scientific article; zbMATH DE number 7069796 (Why is no real title available?)
• Binary recurrent words of ultimate complexity n+2
• Sturmian words and constant additive complexity
• scientific article; zbMATH DE number 6004843 (Why is no real title available?)

This page was built for publication: On additive complexity of infinite words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5404275)