On complexity functions of infinite words associated with generalized Dyck languages

摘要

In 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{sup}(b), indexed on the number b > 1 of parenthesis types, such that the growth order of the complexity function of m{sup}(b) is n(logn){sup}2 if b = 1 and n{sup}(1+log_2{sup}b) i b ≥ 2.