Dejean's conjecture and letter frequency

Jérémie Chalopin; Pascal Ochem

Displaying similar documents to “Dejean's conjecture and letter frequency”

Balance properties of the fixed point of the substitution associated to quadratic simple Pisot numbers

Ondřej Turek (2007)

RAIRO - Theoretical Informatics and Applications

Similarity:

In this paper we will deal with the balance properties of the infinite binary words associated to -integers when is a quadratic simple Pisot number. Those words are the fixed points of the morphisms of the type $ϕ (A) = A^{p} B$ , $ϕ (B) = A^{q}$ for $p \in ℕ$ , $q \in ℕ$ , $p \geq q$ , where $β = \frac{p + \sqrt{p^{2} + 4 q}}{2}$ . We will prove that such word is -balanced with $t = 1 + [(p - 1) / (p + 1 - q)]$ . Finally, in the case that it is known [B. Adamczewski, (2002) 197–224] that the fixed point of the substitution $ϕ (A) = A^{p} B$ , $ϕ (B) = A^{q}$ is not -balanced for any . We exhibit an infinite sequence of pairs...

Palindromes in infinite ternary words

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

RAIRO - Theoretical Informatics and Applications

Similarity:

We study infinite words over an alphabet $𝒜$ satisfying the property $𝒫 : 𝒫 (n) + 𝒫 (n + 1) = 1 + # 𝒜 for any n \in ℕ$ , where $𝒫 (n)$ denotes the number of palindromic factors of length occurring in the language of . We study also infinite words satisfying a stronger property $𝒫ℰ$ : every palindrome of has exactly one palindromic extension in . For binary words, the properties $𝒫$ and $𝒫ℰ$ coincide and these properties characterize Sturmian words, i.e., words with the complexity + 1 for any $n \in ℕ$ . In this paper, we focus on ternary infinite...

Two-variable word equations

Lucian Ilie, Wojciech Plandowski (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We consider languages expressed by word equations in two variables and give a complete characterization for their complexity functions, that is, the functions that give the number of words of the same length. Specifically, we prove that there are only five types of complexities: constant, linear, exponential, and two in between constant and linear. For the latter two, we give precise characterizations in terms of the number of solutions of Diophantine equations of certain types. In...

The Fibonacci automorphism of free Burnside groups

Ashot S. Pahlevanyan (2011)

RAIRO - Theoretical Informatics and Applications

Similarity:

We prove that the Fibonacci morphism is an automorphism of infinite order of free Burnside groups for all odd $n \geq 665$ and even $n = 16 k \geq 8000$ .

Balances and Abelian Complexity of a Certain Class of Infinite Ternary Words

Ondřej Turek (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

A word defined over an alphabet $𝒜$ is -balanced ( $ℕ$ ) if for all pairs of factors , of of the same length and for all letters $𝒜$ , the difference between the number of letters in and is less or equal to . In this paper we consider a ternary alphabet $𝒜$ = {, , } and a class of substitutions $ϕ_{p}$ defined by $ϕ_{p}$ () = , $ϕ_{p}$ () = , $ϕ_{p}$ () = where 1. We prove that the fixed point of $ϕ_{p}$ , formally written as $ϕ_{p}^{\infty}$ (), is 3-balanced...

Binary words avoiding the pattern AABBCABBA

Pascal Ochem (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We show that there are three types of infinite words over the two-letter alphabet {0,1} that avoid the pattern . These types, , , and , differ by the factor complexity and the asymptotic frequency of the letter 0. Type has polynomial factor complexity and letter frequency $\frac{1}{2}$ . Type has exponential factor complexity and the frequency of the letter 0 is at least 0.45622 and at most 0.48684. Type is obtained from type ...