• 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. TUCS Technical Reports 629, Turku Centre for Computer Science, 2004.

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)\geq n+1$. We call languages with bounded
complexity {\it periodic} and languages with complexity $f(n)=n+1$
{\it 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.

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tIlSoPe04a,
  title = {Periodic and Sturmian Languages},
  author = {Ilie, Lucian and Marcus, Solomon and Petre, Ion},
  number = {629},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {2004},
  ISBN = {952-12-1443-0},
}

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

Edit publication