Currently displaying 1 – 18 of 18

Showing per page

Order by Relevance | Title | Year of publication

On automatic infinite permutations

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

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...

Acta Arithmetica

On automatic infinite permutations

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...

Primitive substitutive numbers are closed under rational multiplication

Journal de théorie des nombres de Bordeaux

Let $M\left(r\right)$ denote the set of real numbers $\alpha$ whose base-$r$ digit expansion is ultimately primitive substitutive, i.e., contains a tail which is the image (under a letter to letter morphism) of a fixed point of a primitive substitution. We show that the set $M\left(r\right)$ is closed under multiplication by rational numbers, but not closed under addition.

A note on a conjecture of Duval and sturmian words

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

We prove a long standing conjecture of Duval in the special case of sturmian words.

On the Number of Partitions of an Integer in the $m$-bonacci Base

Annales de l’institut Fourier

For each $m\ge 2,$ we consider the $m$-bonacci numbers defined by ${F}_{k}={2}^{k}$ for $0\le k\le m-1$ and ${F}_{k}={F}_{k-1}+{F}_{k-2}+\cdots +{F}_{k-m}$ for $k\ge m.$ When $m=2,$ these are the usual Fibonacci numbers. Every positive integer $n$ may be expressed as a sum of distinct $m$-bonacci numbers in one or more different ways. Let ${R}_{m}\left(n\right)$ be the number of partitions of $n$ as a sum of distinct $m$-bonacci numbers. Using a theorem of Fine and Wilf, we obtain a formula for ${R}_{m}\left(n\right)$ involving sums of binomial coefficients modulo $2.$ In addition we show that this formula may be used to determine the number of partitions...

A Note on a Conjecture of Duval and Sturmian Words

RAIRO - Theoretical Informatics and Applications

We prove a long standing conjecture of Duval in the special case of Sturmian words.

Eigenvalues and simplicity of interval exchange transformations

Annales scientifiques de l'École Normale Supérieure

For a class of $d$-interval exchange transformations, which we call the symmetric class, we define a new self-dual induction process in which the system is successively induced on a union of sub-intervals. This algorithm gives rise to an underlying graph structure which reflects the dynamical behavior of the system, through the Rokhlin towers of the induced maps. We apply it to build a wide assortment of explicit examples on four intervals having different dynamical properties: these include the first...

Standard factors of Sturmian words

RAIRO - Theoretical Informatics and Applications

Among the various ways to construct a characteristic Sturmian word, one of the most used consists in defining an infinite sequence of prefixes that are standard. Nevertheless in any characteristic word , some standard words occur that are not prefixes of . We characterize all standard words occurring in any characteristic word (and so in any Sturmian word) using firstly morphisms, then standard prefixes and finally palindromes.

Structure of three interval exchange transformations I: an arithmetic study

Annales de l’institut Fourier

In this paper we describe a $2$-dimensional generalization of the Euclidean algorithm which stems from the dynamics of $3$-interval exchange transformations. We investigate various diophantine properties of the algorithm including the quality of simultaneous approximations. We show it verifies the following Lagrange type theorem: the algorithm is eventually periodic if and only if the parameters lie in the same quadratic extension of $ℚ.$

Imbalances in Arnoux-Rauzy sequences

Annales de l'institut Fourier

In a 1982 paper Rauzy showed that the subshift $\left(X,T\right)$ generated by the morphism $1↦12$, $2↦13$ and $3↦1$ is a natural coding of a rotation on the two-dimensional torus ${𝕋}^{2}$, i.e., is measure-theoretically conjugate to an exchange of three fractal domains on a compact set in ${ℝ}^{2},$ each domain being translated by the same vector modulo a lattice. It was believed more generally that each sequence of block complexity $2n+1$ satisfying a combinatorial criterion known as the $☆$ condition of Arnoux and Rauzy codes the orbit of a point...

On some problems related to palindrome closure

RAIRO - Theoretical Informatics and Applications

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 , 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 from...

Page 1