Article ID Journal Published Year Pages File Type
435482 Theoretical Computer Science 2009 16 Pages PDF
Abstract

Let the (subword) complexity of a sequence over a finite set Σ be the function , where denotes the number of distinct blocks u(n)⋯u(n+m−1) of size m in . In this paper, we study the complexity of when each , i=1,…,r, is a qi-automatic sequence over a finite set Σi and q1,…,qr≥2 are pairwise coprime integers. As an application, we answer a question of Allouche and Shallit regarding morphic real numbers.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics