Browse ORBi by ORBi project

- Background
- Content
- Benefits and challenges
- Legal aspects
- Functions and services
- Team
- Help and tutorials

A characterization of multidimensional S-automatic sequences Charlier, Emilie ; Kärki, Tomi ; Rigo, Michel in Actes des rencontres du CIRM, 1 (2009) An infinite word is S-automatic if, for all n ≥ 0, its (n + 1)st letter is the output of a deterministic automaton fed with the representation of n in the considered numeration system S. In this extended ... [more ▼] An infinite word is S-automatic if, for all n ≥ 0, its (n + 1)st letter is the output of a deterministic automaton fed with the representation of n in the considered numeration system S. In this extended abstract, we consider an analogous definition in a multidimensional setting and present the connection to the shape-symmetric infinite words introduced by Arnaud Maes. More precisely, for d ≥ 2, we state that a multidimensional infinite word x : N^d → \Sigma over a finite alphabet \Sigma is S-automatic for some abstract numeration system S built on a regular language containing the empty word if and only if x is the image by a coding of a shape-symmetric infinite word. [less ▲] Detailed reference viewed: 42 (14 ULg)Multidimensional generalized automatic sequences and shape-symmetric morphic words Charlier, Emilie ; ; Rigo, Michel in Proceedings of AutoMathA (2009) An infinite word is S-automatic if, for all n ≥ 0, its (n + 1)st letter is the output of a deterministic automaton fed with the representation of n in the considered numeration system S. In this paper, we ... [more ▼] An infinite word is S-automatic if, for all n ≥ 0, its (n + 1)st letter is the output of a deterministic automaton fed with the representation of n in the considered numeration system S. In this paper, we consider an analogous definition in a multidimensional setting and study the relationship with the shape-symmetric infinite words as introduced by Arnaud Maes. Precisely, for d ≥ 2, we show that a multidimensional infinite word x : N^d → Σ over a finite alphabet Σ is S-automatic for some abstract numeration system S built on a regular language containing the empty word if and only if x is the image by a coding of a shape-symmetric infinite word. [less ▲] Detailed reference viewed: 18 (2 ULg)A Decision Problem for Ultimately Periodic Sets in Non-standard Numeration Systems ; Charlier, Emilie ; et al in International Journal of Algebra & Computation (2009), 19 Consider a non-standard numeration system like the one built over the Fibonacci sequence where nonnegative integers are represented by words over {0,1} without two consecutive 1. Given a set X of integers ... [more ▼] Consider a non-standard numeration system like the one built over the Fibonacci sequence where nonnegative integers are represented by words over {0,1} without two consecutive 1. Given a set X of integers such that the language of their greedy representations in this system is accepted by a finite automaton, we consider the problem of deciding whether or not X is a finite union of arithmetic progressions. We obtain a decision procedure for this problem, under some hypothesis about the considered numeration system. In a second part, we obtain an analogous decision result for a particular class of abstract numeration systems built on an infinite regular language. [less ▲] Detailed reference viewed: 76 (29 ULg)A decision problem for ultimately periodic sets in non-standard numeration systems Charlier, Emilie Scientific conference (2008, December) Given a linear numeration system U and a set X (include in N) such that repU(X) is recognized by a (deterministic) finite automaton. Is it decidable whether or not X is ultimately periodic, i.e., whether ... [more ▼] Given a linear numeration system U and a set X (include in N) such that repU(X) is recognized by a (deterministic) finite automaton. Is it decidable whether or not X is ultimately periodic, i.e., whether or not X is a finite union of arithmetic progressions? Honkala showed that this problem turns out to be decidable for the usual b-ary numeration system (b greater than 2) defined by U_n = bU_{n-1} for n greater than 1 and U_0 = 1. In this work, we give a decision procedure for this problem for a large class of linear numeration systems. [less ▲] Detailed reference viewed: 16 (1 ULg)A decision problem for ultimately periodic sets in non-standard numeration systems Charlier, Emilie Conference (2008, May) We consider the following decidability problem: Given a linear numeration system U and a set X ⊆ N such that rep_U(X) is recognized by a (deterministic) finite automaton. Is it decidable whether or not X ... [more ▼] We consider the following decidability problem: Given a linear numeration system U and a set X ⊆ N such that rep_U(X) is recognized by a (deterministic) finite automaton. Is it decidable whether or not X is ultimately periodic, i.e., whether or not X is a finite union of arithmetic progressions? In this work, we give a decision procedure for this problem whenever U is a linear numeration system such that N is U -recognizable and satisfying a relation of the form U_{i+k} = a_1 U_{i+k−1} + · · · + a_k U_i with a_k = ±1 (the main reason for this assumption is that 1 and −1 are the only two integers invertible modulo n for all n ≥ 2). [less ▲] Detailed reference viewed: 21 (4 ULg)Systèmes de numération Charlier, Emilie Scientific conference (2008, February) Dans cet exposé, je propose une introduction aux systèmes de numération en général : bases entières, numérations linéaires, numérations abstraites. Je donnerai les premiers résultats et attirerai l ... [more ▼] Dans cet exposé, je propose une introduction aux systèmes de numération en général : bases entières, numérations linéaires, numérations abstraites. Je donnerai les premiers résultats et attirerai l'attention sur différents axes de recherche possibles. [less ▲] Detailed reference viewed: 6 (1 ULg)Abstract numeration systems on bounded languages and multiplication by a constant Charlier, Emilie ; Rigo, Michel ; in INTEGERS: Electronic Journal of Combinatorial Number Theory (2008), 8(1-A35), 1-19 A set of integers is $S$-recognizable in an abstract numeration system $S$ if the language made up of the representations of its elements is accepted by a finite automaton. For abstract numeration systems ... [more ▼] A set of integers is $S$-recognizable in an abstract numeration system $S$ if the language made up of the representations of its elements is accepted by a finite automaton. For abstract numeration systems built over bounded languages with at least three letters, we show that multiplication by an integer $\lambda\ge2$ does not preserve $S$-recognizability, meaning that there always exists a $S$-recognizable set $X$ such that $\lambda X$ is not $S$-recognizable. The main tool is a bijection between the representation of an integer over a bounded language and its decomposition as a sum of binomial coefficients with certain properties, the so-called combinatorial numeration system. [less ▲] Detailed reference viewed: 43 (7 ULg)A decision problem for ultimately periodic sets in non-standard numeration systems Charlier, Emilie ; Rigo, Michel in Actes des Journées Montoises d'Informatique Théorique (2008) Consider a non-standard numeration system like the one built over the Fibonacci sequence where nonnegative integers are represented by words over {0, 1} without two consecutive 1. Given a set X of ... [more ▼] Consider a non-standard numeration system like the one built over the Fibonacci sequence where nonnegative integers are represented by words over {0, 1} without two consecutive 1. Given a set X of integers such that the language of their greedy representations in this system is accepted by a finite automaton, we consider the problem of deciding whether or not X is a finite union of arithmetic progressions. We obtain a decision procedure under some hypothesis about the considered numeration system. In a second part, we obtain an analogous decision result for a particular class of abstract numeration systems built on an infinite regular language. [less ▲] Detailed reference viewed: 24 (2 ULg)A Decision Problem for Ultimately Periodic Sets in Non-standard Numeration Systems Charlier, Emilie ; Rigo, Michel in Lecture Notes in Computer Science (2008), 5162 Consider a non-standard numeration system like the one built over the Fibonacci sequence where nonnegative integers are represented by words over {0, 1} without two consecutive 1. Given a set X of ... [more ▼] Consider a non-standard numeration system like the one built over the Fibonacci sequence where nonnegative integers are represented by words over {0, 1} without two consecutive 1. Given a set X of integers such that the language of their greedy representations in this system is accepted by a finite automaton, we consider the problem of deciding whether or not X is a finite union of arithmetic progressions. We obtain a decision procedure under some hypothesis about the considered numeration system. In a second part, we obtain an analogous decision result for a particular class of abstract numeration systems built on an infinite regular language. [less ▲] Detailed reference viewed: 24 (11 ULg)Abstract numeration systems Charlier, Emilie Conference (2007, May) In this talk, I will introduce abstract numeration systems in general and present some results I have regarding operation preserving regularity. In particular, I will focus on multiplication by a constant. Detailed reference viewed: 11 (1 ULg)Structural properties of bounded languages with respect to multiplication by a constant Charlier, Emilie Conference (2007, April) Generalizations of positional number systems in which N is recognizable by finite automata are obtained by describing an arbitrary infinite regular language according to the genealogical ordering. More ... [more ▼] Generalizations of positional number systems in which N is recognizable by finite automata are obtained by describing an arbitrary infinite regular language according to the genealogical ordering. More precisely, an abstract numeration system is a triple S = (L, Σ, <) where L is an infinite language over the totally ordered alphabet (Σ, <). Enumerating the elements of L genealogically with respect to < leads to a one-to-one map rS from N onto L. To any natural number n, it assigns the (n + 1)th word of L, its S-representation, while the inverse map valS sends any word belonging to L onto its numerical value. A subset X is said to be S-recognizable if rS (X) is a regular subset of L. We study the preservation of recognizability of a set of integers after multiplication by a constant for abstract numeration systems built over a bounded language. [less ▲] Detailed reference viewed: 11 (4 ULg)Abstract numeration systems and recognizability Charlier, Emilie Conference (2007, January) In this talk, I will present some results concerning multiplication by a constant in an abstract numeration system built on a bounded language. More precisely, we will show that this operation does not ... [more ▼] In this talk, I will present some results concerning multiplication by a constant in an abstract numeration system built on a bounded language. More precisely, we will show that this operation does not preserve regularity, and therefore cannot be computed by a finite automaton. [less ▲] Detailed reference viewed: 10 (1 ULg)Strutural properties of bounded languages with respect to multiplication by a constant Charlier, Emilie Conference (2006, October) We consider the preservation of recognizability of a set of integers after multiplication by a constant for numeration systems built over a bounded language. As a corollary we show that any nonnegative ... [more ▼] We consider the preservation of recognizability of a set of integers after multiplication by a constant for numeration systems built over a bounded language. As a corollary we show that any nonnegative integer can be written as a sum of binomial coefficients with some prescribed properties. [less ▲] Detailed reference viewed: 23 (3 ULg)Conservation du caractère reconnaissable par opérations arithmétiques dans un système de numération abstrait Charlier, Emilie Master of advanced studies dissertation (2006) In this thesis, I study the stability of recognizability under arithmetic operations like addition, multiplication by a constant or multiplication, in an abstract numeration system. The main result ... [more ▼] In this thesis, I study the stability of recognizability under arithmetic operations like addition, multiplication by a constant or multiplication, in an abstract numeration system. The main result presented in this work concerns the abstract numeration system built on the bounded language a^*b^*. It shows that, in this case, multiplication by a constant preserves recognizability if and only if this constant is an odd square. I end this text by providing some partial results of a generalization to abstract numeration system built on any bounded language. [less ▲] Detailed reference viewed: 48 (4 ULg)Structural properties of bounded languages with respect to multiplication by a constant Charlier, Emilie ; Rigo, Michel in Actes des Journées Montoises d'Informatique Théorique (2006) We consider the preservation of recognizability of a set of integers after multiplication by a constant for numeration systems built over a bounded language. As a corollary we show that any nonnegative ... [more ▼] We consider the preservation of recognizability of a set of integers after multiplication by a constant for numeration systems built over a bounded language. As a corollary we show that any nonnegative integer can be written as a sum of binomial coefficients with some prescribed properties. [less ▲] Detailed reference viewed: 26 (1 ULg)Multiplication by a Constant and Recognizability in an Abstract Numeration System Charlier, Emilie Poster (2005, September 12) One of the main interesting concerns in work about numeration systems is studying the relationship that exist between arithmetic properties of numbers and syntactical properties of their representation ... [more ▼] One of the main interesting concerns in work about numeration systems is studying the relationship that exist between arithmetic properties of numbers and syntactical properties of their representation. More precisely, we prefer to manipulate set of numbers whose representations are characterized by very simple syntactical rules, that is, forming a regular language. Such sets are called S-recognizable sets, where S is the numeration system we are working with. In particular, we would like to obtain numeration systems in which the whole set N is recognizable, partly due to the fact that, if the set of representations of all integers is regular, there are very simple algorithms making it possible to decide if a word stands or does not stand for a number. Some general questions in this area are the following. • Characterization of the recognizable parts in a fixed numeration system. • Determination of the numeration systems for which a given set of numbers is recognizable. • To examine the stability of recognizability under arithmetic operations. In this poster we present our research about that last problem. First, we will define the abstract numeration systems based on a regular language. Then we will study the relationship between multiplication by a constant and the S-recognizability for languages of the type a_1^∗ . . . a_k^∗. [less ▲] Detailed reference viewed: 21 (2 ULg)Systèmes de numération et reconnaissabilité Charlier, Emilie Scientific conference (2005, April) Detailed reference viewed: 3 (0 ULg)Frames d'exponentielles Charlier, Emilie Master's dissertation (2004) Actuellement, la théorie des frames est utilisée principalement en analyse du signal. La découverte du lien entre les frames et les ondelelettes et les bases de Riesz a marqué le point de départ de ... [more ▼] Actuellement, la théorie des frames est utilisée principalement en analyse du signal. La découverte du lien entre les frames et les ondelelettes et les bases de Riesz a marqué le point de départ de l’essor de la théorie des frames dans ce domaine. C’est dans le contexte de l’étude des séries nonharmoniques de Fourier que les frames ont été introduites par R.J. Duffin et A.C. Schaeffer en 1952 dans leur article intitulé "A class of nonharmonic Fourier series". Bien que la définition générale d’une frame sur un espace de Hilbert soit déjà donnée dans cet article et qu’une théorie des frames en elle-même y soit déjà développée, les auteurs, concernés surtout par l’analyse nonharmonique de Fourier, y développent essentiellement la notion de frames d’exponentielles dans l’espace L^2(I), où I est un intervalle borné de R. Le résultat principal obtenu par Duffin et Schaeffer est une condition suffisante pour qu’une suite de nombres complexes génère une frame d’exponentielles. Ce résultat est basé sur un résultat reliant les suites de densité uniforme et les fonctions entières de type exponentiel. Duffin et Schaeffer auteurs ne présentant qu’une condition suffisante, ils laissent donc là un problème ouvert : la caractérisation des frames d’exponentielles. Une résolution partielle de ce problème n’a été donnée que bien plus tard par Jaffard. En effet, en 1991, dans son article "A density criterion for frames of complex exponentials", Jaffard propose une condition nécessaire et suffisante pour qu’une suite réelle génère une frame d’exponentielles. Le but de ce mémoire est de présenter ces résultats. [less ▲] Detailed reference viewed: 63 (8 ULg) |
||