We survey several quantitative problems on infinite words related to repetitions, recurrence, and palindromes, for which the Fibonacci word often exhibits extremal behaviour.

In this paper we study bi-infinite words on two letters. We say that such a word has stiffness $k$ if the number of different subwords of length $n$ equals $n+k$ for all $n$ sufficiently large. The word is called $k$-balanced if the numbers of occurrences of the symbol a in any two subwords of the same length differ by at most $k$. In the present paper we give a complete description of the class of bi-infinite words of stiffness $k$ and show that the number of subwords of length $n$ from this class has growth order...

In this note we consider the longest word, which has periods p1,...,pn, and does not have the period gcd(p1,...,pn). The length of such a word can be established by a simple algorithm. We give a short and natural way to prove that the algorithm is correct. We also give a new proof that the maximal word is a palindrome.

Two linear numeration systems, with characteristic polynomial equal to the minimal polynomial of two Pisot numbers $\beta$ and $\gamma$ respectively, such that $\beta$ and $\gamma$ are multiplicatively dependent, are considered. It is shown that the conversion between one system and the other one is computable by a finite automaton. We also define a sequence of integers which is equal to the number of periodic points of a sofic dynamical system associated with some Parry number.

Two linear numeration systems, with characteristic polynomial equal to the minimal polynomial of two Pisot numbers β and γ respectively, such that β and γ are multiplicatively dependent, are considered. It is shown that the conversion between one system and the other one is computable by a finite automaton. We also define a sequence of integers which is equal to the number of periodic points of a sofic dynamical system associated with some Parry number.

The arithmetical complexity of infinite words, defined by Avgustinovich, Fon-Der-Flaass and the author in 2000, is the number of words of length n which occur in the arithmetical subsequences of the infinite word. This is one of the modifications of the classical function of subword complexity, which is equal to the number of factors of the infinite word of length n. In this paper, we show that the orders of growth of the arithmetical complexity can behave as many sub-polynomial functions. More...

In this paper, we solve some open problems related to (pseudo)palindrome closure operators and to the infinite words generated by their iteration, that is, standard episturmian and pseudostandard words. We show that if ϑ is an involutory antimorphism of A*, then the right and left ϑ-palindromic closures of any factor of a ϑ-standard word are also factors of some ϑ-standard word. We also introduce the class of pseudostandard words with “seed”, obtained by iterated pseudopalindrome closure starting...

We study the functional equation: $\left(1\right)ABC=CDA$ where $A,B,C$ and $D$ are words over an alphabet $\mathcal{A}$. In particular we prove a «structure result» for the inner factors $B,D$: for suitably chosen words $X,Y,Z$ one has: $\left(2\right)B=XYZ$, $D=ZYX$$ 2 ⁢... On substitution invariant Sturmian words: an application of Rauzy fractals Valérie Berthé, Hiromi Ei, Shunji Ito, Hui Rao (2007) RAIRO - Theoretical Informatics and Applications Sturmian words are infinite words that have exactly n+1 factors of length n for every positive integer n. A Sturmian word sα,p is also defined as a coding over a two-letter alphabet of the orbit of point ρ under the action of the irrational rotation Rα : x → x + α (mod 1). A substitution fixes a Sturmian word if and only if it is invertible. The main object of the present paper is to investigate Rauzy fractals associated with two-letter invertible substitutions. As an application, we give... On synchronized sequences and their separators Arturo Carpi, Cristiano Maggi (2001) RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications We introduce the notion of a k -synchronized sequence, where k is an integer larger than 1. Roughly speaking, a sequence of natural numbers is said to be k -synchronized if its graph is represented, in base k , by a right synchronized rational relation. This is an intermediate notion between k -automatic and k -regular sequences. Indeed, we show that the class of k -automatic sequences is equal to the class of bounded k -synchronized sequences and that the class of k -synchronized sequences is strictly... On synchronized sequences and their separators Arturo Carpi, Cristiano Maggi (2010) RAIRO - Theoretical Informatics and Applications We introduce the notion of a k-synchronized sequence, where k is an integer larger than 1. Roughly speaking, a sequence of natural numbers is said to be k-synchronized if its graph is represented, in base k, by a right synchronized rational relation. This is an intermediate notion between k-automatic and k-regular sequences. Indeed, we show that the class of k-automatic sequences is equal to the class of bounded k-synchronized sequences and that the class of k-synchronized sequences is... On ternary square-free circular words. Shur, Arseny M. (2010) The Electronic Journal of Combinatorics [electronic only] Currently displaying 21 – 40 of 67 Previous Page 2 Next $