On a characteristic property of Arnoux–Rauzy sequences
Here we give a characterization of Arnoux–Rauzy sequences by the way of the lexicographic orderings of their alphabet.
On a characteristic property of ARNOUX–RAUZY sequences
Here we give a characterization of Arnoux–Rauzy sequences by the way of the lexicographic orderings of their alphabet.
On a class of Thue-Morse type sequences.
On a code problem concerning planar acyclic graphs
On a devil’s staircase associated to the joint spectral radii of a family of pairs of matrices
The joint spectral radius of a finite set of real matrices is defined to be the maximum possible exponential rate of growth of products of matrices drawn from that set. In previous work with K. G. Hare and J. Theys we showed that for a certain one-parameter family of pairs of matrices, this maximum possible rate of growth is attained along Sturmian sequences with a certain characteristic ratio which depends continuously upon the parameter. In this note we answer some open questions from that paper...
On a generalization of perfect -matching
The paper is concerned with the existence of non-negative or positive solutions to , where is the vertex-edge incidence matrix of an undirected graph. The paper gives necessary and sufficient conditions for the existence of such a solution.
On a paper by Castelli, Mignosi, Restivo
On a paper by Castelli, Mignosi, Restivo
Fine and Wilf's theorem has recently been extended to words having three periods. Following the method of the authors we extend it to an arbitrary number of periods and deduce from that a characterization of generalized Arnoux-Rauzy sequences or episturmian infinite words.
On abelian repetition threshold
We study the avoidance of Abelian powers of words and consider three reasonable generalizations of the notion of Abelian power to fractional powers. Our main goal is to find an Abelian analogue of the repetition threshold, i.e., a numerical value separating k-avoidable and k-unavoidable Abelian powers for each size k of the alphabet. We prove lower bounds for the Abelian repetition threshold for large alphabets and all definitions of Abelian fractional power. We develop a method estimating the exponential...
On Abelian repetition threshold
We study the avoidance of Abelian powers of words and consider three reasonable generalizations of the notion of Abelian power to fractional powers. Our main goal is to find an Abelian analogue of the repetition threshold, i.e., a numerical value separating k-avoidable and k-unavoidable Abelian powers for each size k of the alphabet. We prove lower bounds for the Abelian repetition threshold for large alphabets and all definitions of Abelian fractional ...
On abelian versions of critical factorization theorem
In the paper we study abelian versions of the critical factorization theorem. We investigate both similarities and differences between the abelian powers and the usual powers. The results we obtained show that the constraints for abelian powers implying periodicity should be quite strong, but still natural analogies exist.
On abelian versions of critical factorization theorem∗
In the paper we study abelian versions of the critical factorization theorem. We investigate both similarities and differences between the abelian powers and the usual powers. The results we obtained show that the constraints for abelian powers implying periodicity should be quite strong, but still natural analogies exist.
On an algorithm for a double-resolvability test.
On automatic infinite permutations∗
An infinite permutation α is a linear ordering of N. We study properties of infinite permutations analogous to those of infinite words, and show some resemblances and some differences between permutations and words. In this paper, we try to extend to permutations the notion of automaticity. As we shall show, the standard definitions which are equivalent in the case of words are not equivalent in the context of permutations. We investigate the relationships...
On automatic infinite permutations
An infinite permutation α is a linear ordering of N. We study properties of infinite permutations analogous to those of infinite words, and show some resemblances and some differences between permutations and words. In this paper, we try to extend to permutations the notion of automaticity. As we shall show, the standard definitions which are equivalent in the case of words are not equivalent in the context of permutations. We investigate the relationships between these definitions and prove that...
On automatic infinite permutations∗
An infinite permutation α is a linear ordering of N. We study properties of infinite permutations analogous to those of infinite words, and show some resemblances and some differences between permutations and words. In this paper, we try to extend to permutations the notion of automaticity. As we shall show, the standard definitions which are equivalent in the case of words are not equivalent in the context of permutations. We investigate the relationships...
On bandwidth, cutwidth, and quotient graphs
On binary trees and Dyck paths
A bijection between the set of binary trees with n vertices and the set of Dyck paths of length 2n is obtained. Two constructions are given which enable to pass from a Dyck path to a binary tree and from a binary tree to a Dyck path.
On Christoffel classes
We characterize conjugation classes of Christoffel words (equivalently of standard words) by the number of factors. We give several geometric proofs of classical results on these words and sturmian words.
On Christoffel classes
We characterize conjugation classes of Christoffel words (equivalently of standard words) by the number of factors. We give several geometric proofs of classical results on these words and sturmian words.