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},
}