## Currently displaying 1 – 16 of 16

Showing per page

Order by Relevance | Title | Year of publication

### Langages très simples générateurs

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

### Grammaires algébriques et monoïdes simplifiables

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

### On multiplicatively dependent linear numeration systems, and periodic points

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

Two linear numeration systems, with characteristic polynomial equal to the minimal polynomial of two Pisot numbers $\beta$ and $\gamma$ respectively, such that $\beta$ and $\gamma$ are multiplicatively dependent, are considered. It is shown that the conversion between one system and the other one is computable by a finite automaton. We also define a sequence of integers which is equal to the number of periodic points of a sofic dynamical system associated with some Parry number.

### On-line finite automata for addition in some numeration systems

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

### On multiplicatively dependent linear numeration systems, and periodic points

RAIRO - Theoretical Informatics and Applications

Two linear numeration systems, with characteristic polynomial equal to the minimal polynomial of two Pisot numbers and respectively, such that and are multiplicatively dependent, are considered. It is shown that the conversion between one system and the other one is computable by a finite automaton. We also define a sequence of integers which is equal to the number of periodic points of a sofic dynamical system associated with some Parry number.

### On-line finite automata for addition in some numeration systems

RAIRO - Theoretical Informatics and Applications

We consider numeration systems where the base is a negative integer, or a complex number which is a root of a negative integer. We give parallel algorithms for addition in these numeration systems, from which we derive on-line algorithms realized by finite automata. A general construction relating addition in base and addition in base is given. Results on addition in base $\beta =\sqrt[m]{b}$, where is a relative integer, follow. We also show that addition in base the golden ratio is computable by an on-line...

### Rational base number systems for p-adic numbers

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

This paper deals with rational base number systems for -adic numbers. We mainly focus on the system proposed by Akiyama in 2008, but we also show that this system is in some sense isomorphic to some other rational base number systems by means of finite transducers. We identify the numbers with finite and eventually periodic representations and we also determine the number of representations of a given -adic number.

### Rational base number systems for -adic numbers

RAIRO - Theoretical Informatics and Applications

This paper deals with rational base number systems for -adic numbers. We mainly focus on the system proposed by Akiyama in 2008, but we also show that this system is in some sense isomorphic to some other rational base number systems by means of finite transducers. We identify the numbers with finite and eventually periodic representations and we also determine the number of representations of a given -adic number.

### Complexity of infinite words associated with beta-expansions

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

We study the complexity of the infinite word ${u}_{\beta }$ associated with the Rényi expansion of $1$ in an irrational base $\beta >1$. When $\beta$ is the golden ratio, this is the well known Fibonacci word, which is sturmian, and of complexity $ℂ\left(n\right)=n+1$. For $\beta$ such that ${d}_{\beta }\left(1\right)={t}_{1}{t}_{2}\cdots {t}_{m}$ is finite we provide a simple description of the structure of special factors of the word ${u}_{\beta }$. When ${t}_{m}=1$ we show that $ℂ\left(n\right)=\left(m-1\right)n+1$. In the cases when ${t}_{1}={t}_{2}=\cdots ={t}_{m-1}$ or ${t}_{1}>max\left\{{t}_{2},\cdots ,{t}_{m-1}\right\}$ we show that the first difference of the complexity function $ℂ\left(n+1\right)-ℂ\left(n\right)$ takes value in $\left\{m-1,m\right\}$ for every $n$, and consequently we determine...

### Corrigendum : “Complexity of infinite words associated with beta-expansions”

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

We add a sufficient condition for validity of Propo- sition 4.10 in the paper Frougny et al. (2004). This condition is not a necessary one, it is nevertheless convenient, since anyway most of the statements in the paper Frougny et al. (2004) use it.

### Complexity of infinite words associated with beta-expansions

RAIRO - Theoretical Informatics and Applications

We study the complexity of the infinite word associated with the Rényi expansion of in an irrational base . When is the golden ratio, this is the well known Fibonacci word, which is Sturmian, and of complexity . For such that is finite we provide a simple description of the structure of special factors of the word . When =1 we show that . In the cases when or max} we show that the first difference of the complexity function takes value in for every , and consequently we determine the complexity...

### Corrigendum: Complexity of infinite words associated with beta-expansions

RAIRO - Theoretical Informatics and Applications

We add a sufficient condition for validity of Propo- sition 4.10 in the paper Frougny (2004). This condition is not a necessary one, it is nevertheless convenient, since anyway most of the statements in the paper Frougny (2004) use it.

### Palindromic complexity of infinite words associated with simple Parry numbers

Annales de l’institut Fourier

A simple Parry number is a real number $\beta >1$ such that the Rényi expansion of $1$ is finite, of the form ${d}_{\beta }\left(1\right)={t}_{1}\cdots {t}_{m}$. We study the palindromic structure of infinite aperiodic words ${u}_{\beta }$ that are the fixed point of a substitution associated with a simple Parry number $\beta$. It is shown that the word ${u}_{\beta }$ contains infinitely many palindromes if and only if ${t}_{1}={t}_{2}=\cdots ={t}_{m-1}\ge {t}_{m}$. Numbers $\beta$ satisfying this condition are the so-called Pisot numbers. If ${t}_{m}=1$ then ${u}_{\beta }$ is an Arnoux-Rauzy word. We show that if $\beta$ is a confluent Pisot number then $𝒫\left(n+1\right)+𝒫\left(n\right)=𝒞\left(n+1\right)-𝒞\left(n\right)+2$, where...

Page 1