On complexity functions of infinite words associated with generalized Dyck languages

AbstractIn this article, we construct a family of infinite words, generated by countable automata and also generated by substitutions over infinite alphabets, closely related to parenthesis languages and we study their complexity functions. We obtain a family of binary infinite words m(b), indexed on the number b≥1 of parenthesis types, such that the growth order of the complexity function of m(b) is n(logn)2 if b=1 and n1+log2bb if b≥2