Page 1 Next

Displaying 1 – 20 of 67

Showing per page

On a characteristic property of Arnoux–Rauzy sequences

Jacques Justin, Giuseppe Pirillo (2002)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Here we give a characterization of Arnoux–Rauzy sequences by the way of the lexicographic orderings of their alphabet.

On a devil’s staircase associated to the joint spectral radii of a family of pairs of matrices

Ian D. Morris, Nikita Sidorov (2013)

Journal of the European Mathematical Society

The joint spectral radius of a finite set of real d × d 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 paper by Castelli, Mignosi, Restivo

Jacques Justin (2010)

RAIRO - Theoretical Informatics and Applications

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

Alexey V. Samsonov, Arseny M. Shur (2012)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

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

Alexey V. Samsonov, Arseny M. Shur (2012)

RAIRO - Theoretical Informatics and Applications

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

Sergey Avgustinovich, Juhani Karhumäki, Svetlana Puzynina (2012)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

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∗

Sergey Avgustinovich, Juhani Karhumäki, Svetlana Puzynina (2012)

RAIRO - Theoretical Informatics and Applications

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 automatic infinite permutations∗

Anna Frid, Luca Zamboni (2012)

RAIRO - Theoretical Informatics and Applications

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

Anna Frid, Luca Zamboni (2012)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

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∗

Anna Frid, Luca Zamboni (2012)

RAIRO - Theoretical Informatics and Applications

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 binary trees and Dyck paths

A. Panayotopoulos, A. Sapounakis (1995)

Mathématiques et Sciences Humaines

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

Jean-Pierre Borel, Christophe Reutenauer (2006)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

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

Jean-Pierre Borel, Christophe Reutenauer (2010)

RAIRO - Theoretical Informatics and Applications

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 conjugacy of languages

Julien Cassaigne, Juhani Karhumäki, Ján Maňuch (2001)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

We say that two languages X and Y are conjugates if they satisfy the conjugacy equation X Z = Z Y for some language Z . We study several problems associated with this equation. For example, we characterize all sets which are conjugated v i a a two-element biprefix set Z , as well as all two-element sets which are conjugates.

On Conjugacy of Languages

Julien Cassaigne, Juhani Karhumäki, Ján Maňuch (2010)

RAIRO - Theoretical Informatics and Applications

We say that two languages X and Y are conjugates if they satisfy the conjugacy equationXZ = ZY for some language Z. We study several problems associated with this equation. For example, we characterize all sets which are conjugated via a two-element biprefix set Z, as well as all two-element sets which are conjugates.

On critical exponents in fixed points of k -uniform binary morphisms

Dalia Krieger (2009)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Let 𝐰 be an infinite fixed point of a binary k -uniform morphism f , and let E ( 𝐰 ) be the critical exponent of 𝐰 . We give necessary and sufficient conditions for E ( 𝐰 ) to be bounded, and an explicit formula to compute it when it is. In particular, we show that E ( 𝐰 ) is always rational. We also sketch an extension of our method to non-uniform morphisms over general alphabets.

On Critical exponents in fixed points of k-uniform binary morphisms

Dalia Krieger (2007)

RAIRO - Theoretical Informatics and Applications

Let w be an infinite fixed point of a binary k-uniform morphism f, and let Ew be the critical exponent of w. We give necessary and sufficient conditions for Ew to be bounded, and an explicit formula to compute it when it is. In particular, we show that Ew is always rational. We also sketch an extension of our method to non-uniform morphisms over general alphabets.

Currently displaying 1 – 20 of 67

Page 1 Next