Document Type

Technical Report

Publication Date

Spring 4-1-1980


The subword complexity of a language K is the function which to every positive integer n assigns the number of different subwords of length n occurring in words of K. A language K is square-free if no word in it contains a subword of the form xx where x is a nonempty word. The (best) upper and lower bounds on the subword complexity of infinite square-free DOL languages are established.