Palindromes in infinite ternary words

L'ubomíra Balková; Edita Pelantová; Štěpán Starosta

Displaying similar documents to “Palindromes in infinite ternary words”

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...

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...

Dejean's conjecture and letter frequency

Jérémie Chalopin, Pascal Ochem (2008)

RAIRO - Theoretical Informatics and Applications

Similarity:

We prove two cases of a strong version of Dejean's conjecture involving extremal letter frequencies. The results are that there exist an infinite $({\frac{5}{4}}^{+})$ -free word over a 5 letter alphabet with letter frequency $\frac{1}{6}$ and an infinite $({\frac{6}{5}}^{+})$ -free word over a 6 letter alphabet with letter frequency $\frac{1}{5}$ .

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...

Coalgebras for Binary Methods: Properties of Bisimulations and Invariants

Hendrik Tews (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

Coalgebras for endofunctors $𝒞 \to 𝒞$ can be used to model classes of object-oriented languages. However, binary methods do not fit directly into this approach. This paper proposes an extension of the coalgebraic framework, namely the use of $𝒞^{o p} \times 𝒞 \to 𝒞$ . This extension allows the incorporation of binary methods into coalgebraic class specifications. The paper also discusses how to define bisimulation and invariants for coalgebras of extended polynomial functors and proves many...

The Helping Hierarchy

Patrizio Cintioli, Riccardo Silvestri (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

Schöning [14] introduced a notion of helping and suggested the study of the class $P_{help} (𝒞)$ of the languages that can be helped by oracles in a given class $𝒞$ . Later, Ko [12], in order to study the connections between helping and "witness searching" , introduced the notion of self-helping for languages. We extend this notion to classes of languages and show that there exists a self-helping class that we call SH which contains all the self-helping classes. We introduce the Helping hierarchy whose levels...