The conjugacy map over a Sturmian word.
The problem, generalized Pascal triangles and cellular automata
The box parameter for words and permutations
The box parameter for words counts how often two letters w j and w k define a “box” such that all the letters w j+1; ..., w k−1 fall into that box. It is related to the visibility parameter and other parameters on words. Three models are considered: Words over a finite alphabet, permutations, and words with letters following a geometric distribution. A typical result is: The average box parameter for words over an M letter alphabet is asymptotically given by 2n − 2n H M/M, for fixed M and n → ∞.
The code problem for directed figures
We consider directed figures defined as labelled polyominoes with designated start and end points, with two types of catenation operations. We are especially interested in codicity verification for sets of figures, and we show that depending on the catenation type the question whether a given set of directed figures is a code is decidable or not. In the former case we give a constructive proof which leads to a straightforward algorithm.
The code problem for directed figures
We consider directed figures defined as labelled polyominoes with designated start and end points, with two types of catenation operations. We are especially interested in codicity verification for sets of figures, and we show that depending on the catenation type the question whether a given set of directed figures is a code is decidable or not. In the former case we give a constructive proof which leads to a straightforward algorithm.
The completely distributive lattice of machine invariant sets of infinite words
We investigate the lattice of machine invariant classes. This is an infinite completely distributive lattice but it is not a Boolean lattice. The length and width of it is c. We show the subword complexity and the growth function create machine invariant classes.
The critical exponent of the Arshon words
Generalizing the results of Thue (for n = 2) [Norske Vid. Selsk. Skr. Mat. Nat. Kl. 1 (1912) 1–67] and of Klepinin and Sukhanov (for n = 3) [Discrete Appl. Math. 114 (2001) 155–169], we prove that for all n ≥ 2, the critical exponent of the Arshon word of order n is given by (3n–2)/(2n–2), and this exponent is attained at position 1.
The minimal density of a letter in an infinite ternary square-free word is 883/3215.
The minimal density of a letter in an infinite ternary square-free word is .
The number of binary rotation words
We consider binary rotation words generated by partitions of the unit circle to two intervals and give a precise formula for the number of such words of length n. We also give the precise asymptotics for it, which happens to be Θ(n4). The result continues the line initiated by the formula for the number of all Sturmian words obtained by Lipatov [Problemy Kibernet. 39 (1982) 67–84], then independently by Mignosi [Theoret. Comput. Sci. 82 (1991) 71–84], and others.
The number of positions starting a square in binary words.
The number of ternary words avoiding abelian cubes grows exponentially.
The second-order monadic theory of the free inverse monoid is undecidable. (La théorie monadique du second ordre du monoïde inversif libre est indécidable.)
The subword complexity of a two-parameter family of sequences.
The theorem of Fine and Wilf for relational periods
We consider relational periods, where the relation is a compatibility relation on words induced by a relation on letters. We prove a variant of the theorem of Fine and Wilf for a (pure) period and a relational period.
The theorem of Fine and Wilf for relational periods
We consider relational periods, where the relation is a compatibility relation on words induced by a relation on letters. We prove a variant of the theorem of Fine and Wilf for a (pure) period and a relational period.
The Tribonacci substitution.
There are more than -letter ternary square-free words.
There are ternary circular square-free words of length for 18.
There exist binary circular power free words of every length.