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

Ondřej Turek

Displaying similar documents to “Balances and Abelian Complexity of a Certain Class of 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...

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

Computing the prefix of an automaton

Marie-Pierre Béal, Olivier Carton (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We present an algorithm for computing the prefix of an automaton. Automata considered are non-deterministic, labelled on words, and can have -transitions. The prefix automaton of an automaton $𝒜$ has the following characteristic properties. It has the same graph as $𝒜$ . Each accepting path has the same label as in $𝒜$ . For each state , the longest common prefix of the labels of all paths going from to an initial or final state is empty. The interest of the computation of the prefix...

On-line finite automata for addition in some numeration systems

Christiane Frougny (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We consider numeration systems where the base is a negative integer, or a complex number which is a root of a negative integer. We give parallel algorithms for addition in these numeration systems, from which we derive on-line algorithms realized by finite automata. A general construction relating addition in base and addition in base is given. Results on addition in base $β = \sqrt[m]{b}$ , where is a relative integer, follow. We also show that addition in base the golden ratio is computable...

About the decision of reachability for register machines

Véronique Cortier (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We study the decidability of the following problem: given affine functions ƒ,...,ƒ over $ℕ^{k}$ and two vectors $v_{1}, v_{2} \in ℕ^{k}$ , is reachable from by successive iterations of ƒ,...,ƒ (in this given order)? We show that this question is decidable for and undecidable for some fixed .