Periodic and Sturmian Languages (bibtex)

by Ilie, Lucian, Marcus, Solomon and Petre, Ion

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 functions 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 we characterize the Sturmian languages as the sets of factors of (one- or two-way) infinite Sturmian words.

Reference:

Periodic and Sturmian Languages (Ilie, Lucian, Marcus, Solomon and Petre, Ion), In Information Processing Letters, Elsevier, volume 98, 2006.

Bibtex Entry:

@Article{j32, author = {Ilie, Lucian AND Marcus, Solomon AND Petre, Ion}, title = {Periodic and Sturmian Languages}, journal = {Information Processing Letters}, year = {2006}, volume = {98}, number = {6}, pages = {242-246}, 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 functions 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 we characterize the Sturmian languages as the sets of factors of (one- or two-way) infinite Sturmian words.}, file = {IMP2006b.pdf:pdfs/IMP2006b.pdf:PDF}, keywords = {infinite words, languages, factors, periodic, Sturmian}, publisher = {Elsevier}, }

Powered by bibtexbrowser