| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 438063 | Theoretical Computer Science | 2008 | 17 Pages |
Abstract
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(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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
