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

Introducing Privileged Words: Privileged Complexity of Sturmian Words

Jarkko Peltomäki, Introducing Privileged Words: Privileged Complexity of Sturmian Words. Theoretical Computer Science 500, 57–67, 2013.

http://dx.doi.org/10.1016/j.tcs.2013.05.028

Abstract:

In this paper we introduce a new class of so-called privileged words which have been previously considered only a little. We develop the basic properties of privileged words, which turn out to share similar properties with palindromes. Privileged words are studied in relation to previously studied classes of words, rich words, Sturmian words and episturmian words. A new characterization of Sturmian words is given in terms of privileged complexity. The privileged complexity of the Thue–Morse word is also briefly studied.

BibTeX entry:

@ARTICLE{jPeltomaki_Jarkko13a,
  title = {Introducing Privileged Words: Privileged Complexity of Sturmian Words},
  author = {Peltomäki, Jarkko},
  journal = {Theoretical Computer Science},
  volume = {500},
  publisher = {Elsevier},
  pages = {57–67},
  year = {2013},
  keywords = {combinatorics on words,sturmian words,palindromes,privileged words,return words,rich words},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Publication Forum rating of this publication: level 2

Edit publication