On the subword complexity of the fixed point of a → aab, b → b, and generalizations

2016/05/08 by Allouche, J. -P., Shallit, J.
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #Number Theory (math.NT)

paper · doi:10.48550/arxiv.1605.02361

Abstract

We find an explicit closed form for the subword complexity of the infinite fixed point of the morphism sending a → aab and b → b. This morphism is then generalized in three different ways, and we find similar explicit expressions for the subword complexity of the generalizations.

Related

• On Subword Complexity of Morphic Sequences
• Note on BDL property of fixed points of primitive morphisms
• A Pansiot-type subword complexity theorem for automorphisms of free groups
• Fixed points of morphisms among binary generalized pseudostandard words
• Characterizations of families of morphisms and words via binomial complexities