Search

A frame is a square u u , where u is an unbordered word. Let F ( n ) denote the maximum number of distinct frames in a binary word of length n . We count this number for small values of n and show that F ( n ) is at most ⌊ n / 2 ⌋ + 8 for all n and greater than 7 n / 30 − ϵ for any positive ϵ and infinitely many n . We also show that Fibonacci words, which are known to contain plenty of distinct squares, have only a few frames. Moreover, by modifying the Thue–Morse word, we prove that the minimum number of occurrences of frames in a word of length n is ⌈ n / 2 ⌉ − 2 .

An infinite word is S-automatic if, for all n ≥ 0, its (n + 1)st letter is the output of a deterministic automaton fed with the representation of n in the considered numeration system S. In this extended abstract, we consider an analogous definition in a multidimensional setting and present the connection to the shape-symmetric infinite words introduced by Arnaud Maes. More precisely, for d ≥ 2, we state that a multidimensional infinite word x : N → Σ over a finite alphabet Σ is S-automatic for some abstract numeration system S built on a regular language containing the empty word if and only if x is the image by a coding of a shape-symmetric infinite word.

We consider words, i.e. strings over a finite alphabet together with a similarity relation induced by a compatibility relation on letters. This notion generalizes that of partial words. The theory of codes on combinatorics on words is revisited by defining (R,S)-codes for arbitrary similarity relations R and S. We describe an algorithm to test whether or not a finite set of words is an (R,S)-code. Coding properties of finite sets of words are explored by finding maximal and minimal relations with respect to relational codes.

A similarity relation is a relation on words of equal length induced by a symmetric and reflexive relation on letters. The aim of this article is to give an overview of the results concerning repetition-freeness in connection with similarity relations. We consider so called chain relations, cyclic relations and partial words, which can be seen as a special case of similarity relations. As a new result, we prove that local 3+-repetitions can be avoided in binary partial words and the local avoidability index of $\mathring{R}$ -cubes is five, where $\mathring{R}$ is a relation such that the graph of the relation is a cycle.

We give a new proof for the decidability of the D0L ultimate periodicity problem based on the decidability of p-periodicity of morphic words adapted to the approach of Harju and Linna., In Proceedings WORDS 2011, arXiv:1108.3412

Given a morphism h prolongable on a and an integer p, we present an algorithm that calculates which letters occur infinitely often in congruent positions modulo p in the infinite word hω(a). As a corollary, we show that it is decidable whether a morphic word is ultimately p-periodic. Moreover, using our algorithm we can find the smallest similarity relation such that the morphic word is ultimately relationally p-periodic. The problem of deciding whether an automatic sequence is ultimately weakly R-periodic is also shown to be decidable.

Let I be a finite set of integers and F be a finite set of maps of the form n?k i n + ? i with integer coefficients. For an integer base k ? 2, we study the k-recognizability of the minimal set X of integers containing I and satisfying φ(X) ? X for all φ ? F. In particular, solving a conjecture of Allouche, Shallit and Skordev, we show under some technical conditions that if two of the constants k i are multiplicatively independent, then X is not k-recognizable for any k ? 2.

An infinite word is S-automatic if, for all n>=0, its (n + 1)st letter is the output of a deterministic automaton fed with the representation of n in the considered numeration system S. In this extended abstract, we consider an analogous definition in a multidimensional setting and present the connection to the shape-symmetric infinite words introduced by Arnaud Maes. More precisely, for d>=2, we state that a multidimensional infinite word x : N^d \to \Sigma over a finite alphabet \Sigma is S-automatic for some abstract numeration system S built on a regular language containing the empty word if and only if x is the image by a coding of a shape-symmetric infinite word.

By the famous theorem of Morse and Hedlund, a word is ultimately periodic if and only if it has bounded subword complexity, i.e., for sufficiently large n, the number of factors of length nis constant. In this paper we consider relational periods and relationally periodic sequences, where the relation is a similarity relation on words induced by a compatibility relation on letters. We investigate what would be a suitable definition for a relational subword complexity function such that it would imply a Morse and Hedlund-like theorem for relationally periodic words. We consider strong and weak relational periods and two candidates for subword complexity functions.

Automata, Logic and Semantics, We consider relational periods where the relation is a compatibility relation on words induced by a relation on letters. We introduce three types of periods, namely global, external and local relational periods, and we compare their properties by proving variants of the theorem of Fine and Wilf for these periods.