• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

Periodic and Sturmian Languages

Lucian Ilie, Solomon Marcus, Ion Petre, Periodic and Sturmian Languages. Information Processing Letters 98(6), 242–246, 2006.

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.

BibTeX entry:

@ARTICLE{jIlMaPe06a,
  title = {Periodic and Sturmian Languages},
  author = {Ilie, Lucian and Marcus, Solomon and Petre, Ion},
  journal = {Information Processing Letters},
  volume = {98},
  number = {6},
  pages = {242–246},
  year = {2006},
}

Belongs to TUCS Research Unit(s): Computational Biomodeling Laboratory (Combio Lab)

Publication Forum rating of this publication: level 2

Edit publication