| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 428913 | Information Processing Letters | 2006 | 5 Pages |
Abstract
Counting the number of distinct factors in the words of a language gives a measure of complexity for that language similar to the factor-complexity of infinite words. Similarly as for infinite words, we prove that this complexity function f(n) is either bounded or f(n)⩾n+1. We call languages with bounded complexity periodic and languages with complexity f(n)=n+1 Sturmian. We describe the structure of periodic languages and characterize the Sturmian languages as the sets of factors of (one- or two-way) infinite Sturmian words.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
