Palindromic complexity of infinite words associated with non-simple Parry numbers

L'ubomíra Balková; Zuzana Masáková

Displaying similar documents to “Palindromic complexity of infinite words associated with non-simple Parry numbers”

Complexity of infinite words associated with beta-expansions

Christiane Frougny, Zuzana Masáková, Edita Pelantová (2004)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

We study the complexity of the infinite word $u_{β}$ associated with the Rényi expansion of $1$ in an irrational base $β > 1$ . When $β$ is the golden ratio, this is the well known Fibonacci word, which is sturmian, and of complexity $ℂ (n) = n + 1$ . For $β$ such that $d_{β} (1) = t_{1} t_{2} \dots t_{m}$ is finite we provide a simple description of the structure of special factors of the word $u_{β}$ . When $t_{m} = 1$ we show that $ℂ (n) = (m - 1) n + 1$ . In the cases when $t_{1} = t_{2} = \dots = t_{m - 1}$ or $t_{1} > max {t_{2}, \dots, t_{m - 1}}$ we show that the first difference of the complexity function $ℂ (n + 1) - ℂ (n)$ takes value in ${m - 1, m}$ for every $n$ , and consequently...

Corrigendum : “Complexity of infinite words associated with beta-expansions”

Christiane Frougny, Zuzana Masáková, Edita Pelantová (2004)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

We add a sufficient condition for validity of Propo- sition 4.10 in the paper Frougny et al. (2004). This condition is not a necessary one, it is nevertheless convenient, since anyway most of the statements in the paper Frougny et al. (2004) use it.

Sturmian jungle (or garden?) on multiliteral alphabets

L&amp;#039;ubomíra Balková, Edita Pelantová, Štěpán Starosta (2010)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

The properties characterizing sturmian words are considered for words on multiliteral alphabets. We summarize various generalizations of sturmian words to multiliteral alphabets and enlarge the list of known relationships among these generalizations. We provide a new equivalent definition of rich words and make use of it in the study of generalizations of sturmian words based on palindromes. We also collect many examples of infinite words to illustrate differences in the generalized...

Episturmian words: a survey

Amy Glen, Jacques Justin (2009)

RAIRO - Theoretical Informatics and Applications

Similarity:

In this paper, we survey the rich theory of infinite which generalize to any finite alphabet, in a rather resembling way, the well-known family of on two letters. After recalling definitions and basic properties, we consider that allow for a deeper study of these words. Some properties of factors are described, including factor complexity, palindromes, fractional powers, frequencies, and return words. We also consider lexicographical properties of episturmian words, as well as their...

Standard factors of Sturmian words

Gwénaël Richomme, Kalle Saari, Luca Q. Zamboni (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

Among the various ways to construct a characteristic Sturmian word, one of the most used consists in defining an infinite sequence of prefixes that are standard. Nevertheless in any characteristic word , some standard words occur that are not prefixes of . We characterize all standard words occurring in any characteristic word (and so in any Sturmian word) using firstly morphisms, then standard prefixes and finally palindromes.