References of "Rigo, Michel"      in Complete repository Arts & humanities   Archaeology   Art & art history   Classical & oriental studies   History   Languages & linguistics   Literature   Performing arts   Philosophy & ethics   Religion & theology   Multidisciplinary, general & others Business & economic sciences   Accounting & auditing   Production, distribution & supply chain management   Finance   General management & organizational theory   Human resources management   Management information systems   Marketing   Strategy & innovation   Quantitative methods in economics & management   General economics & history of economic thought   International economics   Macroeconomics & monetary economics   Microeconomics   Economic systems & public economics   Social economics   Special economic topics (health, labor, transportation…)   Multidisciplinary, general & others Engineering, computing & technology   Aerospace & aeronautics engineering   Architecture   Chemical engineering   Civil engineering   Computer science   Electrical & electronics engineering   Energy   Geological, petroleum & mining engineering   Materials science & engineering   Mechanical engineering   Multidisciplinary, general & others Human health sciences   Alternative medicine   Anesthesia & intensive care   Cardiovascular & respiratory systems   Dentistry & oral medicine   Dermatology   Endocrinology, metabolism & nutrition   Forensic medicine   Gastroenterology & hepatology   General & internal medicine   Geriatrics   Hematology   Immunology & infectious disease   Laboratory medicine & medical technology   Neurology   Oncology   Ophthalmology   Orthopedics, rehabilitation & sports medicine   Otolaryngology   Pediatrics   Pharmacy, pharmacology & toxicology   Psychiatry   Public health, health care sciences & services   Radiology, nuclear medicine & imaging   Reproductive medicine (gynecology, andrology, obstetrics)   Rheumatology   Surgery   Urology & nephrology   Multidisciplinary, general & others Law, criminology & political science   Civil law   Criminal law & procedure   Criminology   Economic & commercial law   European & international law   Judicial law   Metalaw, Roman law, history of law & comparative law   Political science, public administration & international relations   Public law   Social law   Tax law   Multidisciplinary, general & others Life sciences   Agriculture & agronomy   Anatomy (cytology, histology, embryology...) & physiology   Animal production & animal husbandry   Aquatic sciences & oceanology   Biochemistry, biophysics & molecular biology   Biotechnology   Entomology & pest control   Environmental sciences & ecology   Food science   Genetics & genetic processes   Microbiology   Phytobiology (plant sciences, forestry, mycology...)   Veterinary medicine & animal health   Zoology   Multidisciplinary, general & others Physical, chemical, mathematical & earth Sciences   Chemistry   Earth sciences & physical geography   Mathematics   Physics   Space science, astronomy & astrophysics   Multidisciplinary, general & others Social & behavioral sciences, psychology   Animal psychology, ethology & psychobiology   Anthropology   Communication & mass media   Education & instruction   Human geography & demography   Library & information sciences   Neurosciences & behavior   Regional & inter-regional studies   Social work & social policy   Sociology & social sciences   Social, industrial & organizational psychology   Theoretical & cognitive psychology   Treatment & clinical psychology   Multidisciplinary, general & others     Showing results 41 to 60 of 120     1 2 3 4 5 6 7     Some properties of abelian return wordsRigo, Michel ; Salimov, Pavel ; Vandomme, Elise in Journal of Integer Sequences (2013), 16We investigate some properties of abelian return words as recently introduced by S. Puzynina and L. Q. Zamboni. In particular, we obtain a characterization of Sturmian words with non-null intercept in ... [more ▼]We investigate some properties of abelian return words as recently introduced by S. Puzynina and L. Q. Zamboni. In particular, we obtain a characterization of Sturmian words with non-null intercept in terms of the finiteness of the set of abelian return words to all prefixes. We describe this set of abelian returns for the Fibonacci word but also for the 2-automatic Thue--Morse word. We also investigate the relationship existing between abelian complexity and finiteness of the set of abelian returns to all prefixes. We end this paper by considering the notion of abelian derived sequence. It turns out that, for the Thue--Morse word, the set of abelian derived sequences is infinite. [less ▲]Detailed reference viewed: 156 (39 ULiège) Multidimensional extension of the Morse-Hedlund theoremDurand, Fabien; Rigo, Michel in European Journal of Combinatorics (2013), 34Nivat's conjecture is about the link between the pure periodicity of a subset M of Z^2, i.e., invariance under translation by a fixed vector, and some upper bound on the function counting the number of ... [more ▼]Nivat's conjecture is about the link between the pure periodicity of a subset M of Z^2, i.e., invariance under translation by a fixed vector, and some upper bound on the function counting the number of different rectangular blocks occurring in $M$. Attempts to solve this conjecture have been considered during the last fifteen years. Let d>1. A legitimate extension to a multidimensional setting of the notion of periodicity is to consider sets of Z^d definable by a first order formula in the Presburger arithmetic . With this latter notion and using a powerful criterion due to Muchnik, we solve an analogue of Nivat's conjecture and characterize sets of Z^d definable in in terms of some functions counting recurrent blocks, that is, blocks occurring infinitely often. [less ▲]Detailed reference viewed: 73 (8 ULiège) 2-abelian complexity of the Thue-Morse sequenceRigo, Michel ; Vandomme, Elise Scientific conference (2012, December 14)Let k be an integer. Two words u and v of the same length are k-abelian equivalent, if they have the same prefix (resp. suffix) of length k-1 and if, for all words x of length k, the numbers of ... [more ▼]Let k be an integer. Two words u and v of the same length are k-abelian equivalent, if they have the same prefix (resp. suffix) of length k-1 and if, for all words x of length k, the numbers of occurrences of x in u and v are the same. This notion has received some recent interest, see the works of Karhumäki et al. The k-abelian complexity of an infinite word x maps an integer n to the number of k-abelian classes partitioning the set of factors of length n occurring in x. The Thue-Morse word is a well-known and extensively studied 2-automatic sequence. It is trivially abelian periodic and its (1)-abelian complexity takes only two values. The aim of this talk is to explain how to compute the 2-abelian complexity a(n) of the Thue-Morse word, showing in particular that it is unbounded. We conjecture that a(n) is 2-regular in the sense of Allouche and Shallit. This question can be related to a recent work of Madill and Rampersad where the (1)-abelian complexity of the paper folding word is shown to be 2-regular. We will also explain why the usual logical framework introduced by Büchi and popularized by Bruyère (indeed, automatic sequences can be characterized in an extension of the Presburger arithmetic) and the recent work of Charlier et al. about "automatic theorem-proving" of properties of automatic sequences cannot be applied to these questions related to abelian complexity. [less ▲]Detailed reference viewed: 177 (35 ULiège) Numeration systems: a link between number theory and formal language theoryRigo, Michel Scientific conference (2012, November 28)In this talk, we survey facts mostly emerging from the seminal results of Alan Cobham obtained in the late sixties and early seventies about sets of integers whose base k expansions are recognized by some ... [more ▼]In this talk, we survey facts mostly emerging from the seminal results of Alan Cobham obtained in the late sixties and early seventies about sets of integers whose base k expansions are recognized by some finite automaton. We do not expect any background from the audience, so we will present the basic definitions and many examples. We will not attempt to be exhaustive but try instead to present some actual research directions about numeration systems, recognizable sets of integers and automatic sequences. If there is enough time, we will brieﬂy sketch some results about transcendence related to the representation of real numbers. [less ▲]Detailed reference viewed: 86 (6 ULiège) Some properties of abelian return words (long abstract)Rigo, Michel ; Salimov, Pavel ; Vandomme, Elise Conference (2012, September 11)We investigate some properties of abelian return words as recently introduced by Puzynina and Zamboni. In particular, we obtain a characterization of Sturmian words with non-null intercept in terms of the ... [more ▼]We investigate some properties of abelian return words as recently introduced by Puzynina and Zamboni. In particular, we obtain a characterization of Sturmian words with non-null intercept in terms of the ﬁniteness of the set of abelian return words to all preﬁxes. We describe this set of abelian returns for the Fibonacci word but also for the 2-automatic Thue–Morse word. We also investigate the relationship existing between abelian complexity and ﬁniteness of the set of abelian returns to all preﬁxes. We end this paper by considering the notion of abelian derived sequence. It turns out that, for the Thue–Morse word, the set of abelian derived sequences is inﬁnite. [less ▲]Detailed reference viewed: 31 (7 ULiège) On the concrete complexity of the successor functionBerthé, Valérie; Frougny, Christiane; Rigo, Michel et alConference (2012, September 11)We consider two kinds of questions about the successor function. The ﬁrst one is concerned with the estimation of the length of the carry propagation when applying the successor map on the first n ... [more ▼]We consider two kinds of questions about the successor function. The ﬁrst one is concerned with the estimation of the length of the carry propagation when applying the successor map on the first n integers (or more generally on the first n elements in a given language). This leads to the notion of amortized (or average) carry propagation when applying the successor function. The second question is a computational issue: estimating the number of operations (in classical terms of Turing machines complexity) required to compute the representations of the first n integers from the first one by applying n times the successor function. This leads to the notion of (amortized) complexity, i.e., the average amount of computations required to obtain the successor of an element. [less ▲]Detailed reference viewed: 112 (4 ULiège) Le problème de ProuhetRigo, Michel Conference (2012, August 22)Si on pense aux nombres, à leur théorie et à l'arithmétique, on fait rapidement face à de nombreuses questions simples à énoncer (elles ne font intervenir que des sommes, des produits ou des puissances de ... [more ▼]Si on pense aux nombres, à leur théorie et à l'arithmétique, on fait rapidement face à de nombreuses questions simples à énoncer (elles ne font intervenir que des sommes, des produits ou des puissances de nombres entiers) mais leurs éventuelles solutions peuvent s'avérer redoutables. Dans cet exposé, on s'intéressera à un problème accessible dû à Prouhet (1851) : "partitionner l'ensemble {0,1,2,...,2^N-1} en deux sous-ensembles A et B de même taille de telle sorte que les sommes des éléments de A et B soient égales, les sommes des carrés des éléments de A et B soient égales, ..., les sommes des puissances (N-1)-ièmes des éléments de A et B soient égales ". Par exemple, pour N=3, on trouve 0+3+5+6=1+2+4+7 et 0^2+3^2+5^2+6^2=1^2+2^2+4^2+7^2. On en présentera une solution reposant de façon élégante sur les écritures en base 2 et on s'autorisera quelques digressions : produit de sinus, répétition et chevauchement, jeu d'échecs, généralisations, pavages colorés, composition musicale, tours de Hanoï, cubes magiques, ... Cet exposé est construit pour être une balade arithmétique amusante et inattendue, pouvant montrer à des élèves ouverts, un peu comme le prétend André DELEDICQ, que les mathématiques peuvent être jubilatoires. [less ▲]Detailed reference viewed: 89 (12 ULiège) Autour des systèmes de numération abstraitsRigo, Michel Conference (2012, June 12)Un système de numération, comme notre système décimal usuel, peut être vu comme une bijection entre l'ensemble des entiers naturels et le langage formé des représentations de ces entiers. Lorsque l'on ... [more ▼]Un système de numération, comme notre système décimal usuel, peut être vu comme une bijection entre l'ensemble des entiers naturels et le langage formé des représentations de ces entiers. Lorsque l'on considère, de façon générale, une numération basée sur une suite strictement croissante d'entiers et pour laquelle les représentations sont obtenues par un algorithme glouton, la bijection qui à un entier associe sa représentation préserve l'ordre naturel. Ainsi, un système de numération abstrait est la donnée d'un langage L infini (le plus souvent régulier) ordonné par ordre généalogique croissant. L'entier n est alors représenté par le n-ième mot du langage L. L'introduction, il y a une dizaine d'années, de ces systèmes abstraits a été motivée par le théorème de Cobham de 1969 qui s'intéresse aux ensembles reconnaissables d'entiers. Un ensemble X d'entiers est dit S-reconnaissable, pour une numération fixée S, si l'ensemble des représentations dans le système S des éléments de X forme un langage régulier. Ainsi les ensembles S-reconnaissables sont, d'un certain point de vue, particulièrement simples puisque décrits par un automate fini. Le théorème de Cobham stipule que les seuls ensembles d'entiers simultanément reconnaissables pour deux bases entières k et l suffisamment indépendantes, à savoir multiplicativement indépendantes, sont exactement les unions finies de progressions arithmétiques. Ce théorème a été le point de départ de nombreux travaux de recherche au cours de ces quarante dernières années (généralisations à des numérations non standards, à plusieurs dimensions, formalisme logique,... ). Dans ce survol liant théorie élémentaire des nombres et théorie des automates, nous nous proposons de présenter quelques questions et développements en lien directe avec cette question générale : existe-t-il un lien entre les propriétés arithmétiques des nombres (e.g., carré parfait, nombre premier, critère de divisibilité, ...) et les propriétés syntaxiques de leurs représentations ? Les propriétés décrites par automates finis sont-elles, par exemple, stables en appliquant des opérations arithmétiques élémentaires comme l'addition ou la multiplication par une constante ? Les automates permettent également de tracer des liens avec la combinatoire des mots (suites automatiques au sens d'Allouche et Shallit et plus généralement mots morphiques engendrés par substitution) ou d'exprimer certains problèmes de décision dont la solution revient à étudier la complexité en nombre d'états (state complexity) de certaines familles de langages. [less ▲]Detailed reference viewed: 89 (5 ULiège) Recognizable sets of integersRigo, Michel Conference (2012, June)Detailed reference viewed: 70 (0 ULiège) Mathémagie 2Rigo, Michel Speech/Talk (2012)Nous présentons ici des tours de magie ne nécessitant aucune habileté particulière de la part de l'apprenti magicien : des tours de cartes, des tours de divination etc. Contrairement au magicien qui ne ... [more ▼]Nous présentons ici des tours de magie ne nécessitant aucune habileté particulière de la part de l'apprenti magicien : des tours de cartes, des tours de divination etc. Contrairement au magicien qui ne dévoile jamais ses secrets, ici, nous expliquons que ces tours reposent sur diverses propriétés et constructions mathématiques (décomposition d'une permutation en produit de cycle, suites linéaires récurrentes, ...). Il y en aura donc pour tous les goûts... et tous les niveaux. Dans la mesure du possible, nous présenterons de "nouveaux" tours qui n'auraient pas déjà été dévoilés dans un exposé précédent. [less ▲]Detailed reference viewed: 177 (15 ULiège) Le problème de ProuhetRigo, Michel in Losanges (2012), 19Si on pense aux nombres, à leur théorie et à l'arithmétique, on fait rapidement face à de nombreuses questions simples à énoncer (elles ne font intervenir que des sommes, des produits ou des puissances de ... [more ▼]Si on pense aux nombres, à leur théorie et à l'arithmétique, on fait rapidement face à de nombreuses questions simples à énoncer (elles ne font intervenir que des sommes, des produits ou des puissances de nombres entiers) mais leurs éventuelles solutions peuvent s'avérer redoutables. Dans ce texte relatif à mon intervention du 22 août 2012 au congrès annuel de la SBPMef, on s'intéressera à un problème accessible : partitionner l'ensemble {0,1,2,...,2^{n+1}-1} en deux sous-ensembles A et B de même taille de telle sorte que les sommes des éléments de A et B soient égales, les sommes des carrés des éléments de A et B soient égales, ..., les sommes des puissances n-ièmes des éléments de A et B soient égales. Par exemple, pour n=2, on trouve 0+3+5+6=1+2+4+7 et 0^2+3^2+5^2+6^2=1^2+2^2+4^2+7^2. On en présentera une solution reposant de façon élégante sur les écritures en base $2$ et on s'autorisera quelques digressions : produit de sinus, répétition et chevauchement, jeu d'échecs, composition musicale, ... Ce texte est construit pour être une balade arithmétique amusante et inattendue, pouvant montrer à des élèves ouverts, un peu comme le prétend André Deledicq, que les mathématiques peuvent être jubilatoires. [less ▲]Detailed reference viewed: 69 (2 ULiège) Syntactic complexity of ultimately periodic sets of integers and application to a decision procedureLacroix, Anne ; Rampersad, Narad; Rigo, Michel et alin Fundamenta Informaticae (2012), 116We compute the cardinality of the syntactic monoid of the language 0* rep_b(mN) made of base b expansions of the multiples of the integer m. We also give lower bounds for the syntactic complexity of any ... [more ▼]We compute the cardinality of the syntactic monoid of the language 0* rep_b(mN) made of base b expansions of the multiples of the integer m. We also give lower bounds for the syntactic complexity of any (ultimately) periodic set of integers written in base b. We apply our results to a well studied problem: decide whether or not a b-recognizable set of integers is ultimately periodic. [less ▲]Detailed reference viewed: 87 (18 ULiège) Extensions and restrictions of Wythoff's game preserving its P-positionsRigo, Michel Scientific conference (2011, October 21)Wythoff's game is a century old classical two players combinatorial game. When studying this game, Beatty sequences associated with the Golden Ratio, syntactical properties of the representations of ... [more ▼]Wythoff's game is a century old classical two players combinatorial game. When studying this game, Beatty sequences associated with the Golden Ratio, syntactical properties of the representations of integers in the Fibonacci or Zeckendorf numeration system and the morphic Fibonacci word appear naturally in characterizations of its P-positions. Recall that whatever is the move played from a P-position, the other player has a winning strategy. Contrarily to the usual approach where one defines a new game by a set of rules and then tries to characterize the corresponding set of P-positions, our motivations are to proceed the other way around: keep the original set of P-positons while changing the rules. We consider extensions and restrictions of Wythoff's game having exactly the same set of P-positions as the original game. Our results are the following one: no strict subset of rules gives the same set of P-positions. On the other hand, we characterize all moves that can be adjoined while preserving the original set of P-positions. Testing if a move belongs to such an extended set of rules is shown to be done in polynomial time. In this talk, we won't consider many game theoretical aspects (but we will recall some basic facts on combinatorial games). We focus mainly on the role played by numeration systems, regular languages and bidimensional words generated by substitutions/morphisms. Indeed, games like this one provide nice interaction between combinatorics on words and combinatorial game theory. For instance, the set of P-positions of Wythoff's game are "coded" by the infinite Fibonacci word. Therefore, many arguments rely on this word, on automatic sequences and on the corresponding numeration systems. With these tools, we provide new bidimensional (shape-symmetric in the sense of Arnaud Maes) morphisms generating an infinite picture encoding respectively P-positions of Wythoff's game and moves that can be adjoined preserving the same set of P-positions. [less ▲]Detailed reference viewed: 69 (5 ULiège) Syntactic complexity of ultimately periodic sets of integersRigo, Michel ; Vandomme, Elise Conference (2011, June)We compute the cardinality of the syntactic monoid of the language 0^∗rep_b(mN) made of base b expansions of the multiples of the integer m. We also give lower bounds for the syntactic complexity of any ... [more ▼]We compute the cardinality of the syntactic monoid of the language 0^∗rep_b(mN) made of base b expansions of the multiples of the integer m. We also give lower bounds for the syntactic complexity of any (ultimately) periodic set of integers written in base b. We apply our results to some well studied problem: decide whether or not a b-recognizable sets of integers is ultimately periodic. [less ▲]Detailed reference viewed: 18 (4 ULiège) Defining multiplication for polynomials over a finite field.Rigo, Michel ; Waxweiler, LaurentE-print/Working paper (2011)Let $P$ and $Q$ be two non-zero multiplicatively independent polynomials with coefficients in a finite field $\mathbb{F}$. Adapting a result of R.~Villemaire, we show that multiplication of polynomials is ... [more ▼]Let $P$ and $Q$ be two non-zero multiplicatively independent polynomials with coefficients in a finite field $\mathbb{F}$. Adapting a result of R.~Villemaire, we show that multiplication of polynomials is a ternary relation $\{(A,B,C)\in\mathbb{F}[X]\mid A.B=C\}$ definable by a first-order formula in a suitable structure containing both functions $V_P$ and $V_Q$ where $V_A(B)$ is defined as the greatest power of $A$ dividing $B$. Such a result has to be considered in the context of a possible analogue of Cobham's theorem for sets of polynomials whose $P$-expansions are recognized by some finite automaton. [less ▲]Detailed reference viewed: 108 (7 ULiège) Logical characterization of recognizable sets of polynomials over a finite fieldRigo, Michel ; Waxweiler, Laurentin International Journal of Foundations of Computer Science (2011), 22(7), 1549-1563The ring of integers and the ring of polynomials over a finite field share a lot of properties. Using a bounded number of polynomial coefficients, any polynomial can be decomposed as a linear combination ... [more ▼]The ring of integers and the ring of polynomials over a finite field share a lot of properties. Using a bounded number of polynomial coefficients, any polynomial can be decomposed as a linear combination of powers of a non-constant polynomial P playing the role of the base of the numeration. Having in mind the theorem of Cobham from 1969 about recognizable sets of integers, it is natural to study $P$-recognizable sets of polynomials. Based on the results obtained in the Ph.D. thesis of the second author, we study the logical characterization of such sets and related properties like decidability of the corresponding first-order theory. [less ▲]Detailed reference viewed: 118 (12 ULiège) The minimal automaton recognizing mN in a linear numeration systemCharlier, Emilie ; Rampersad, Narad ; Rigo, Michel et alin Integers: Electronic Journal of Combinatorial Number Theory (2011), 11B(A4), 1-24We study the structure of automata accepting the greedy representations of N in a wide class of numeration systems. We describe the conditions under which such automata can have more than one strongly ... [more ▼]We study the structure of automata accepting the greedy representations of N in a wide class of numeration systems. We describe the conditions under which such automata can have more than one strongly connected component and the form of any such additional components. Our characterization applies, in particular, to any automaton arising from a Bertrand numeration system. Furthermore, we show that for any automaton A arising from a system with a dominant root beta>1, there is a morphism mapping A onto the automaton arising from the Bertrand system associated with the number beta. Under some mild assumptions, we also study the state complexity of the trim minimal automaton accepting the greedy representations of the multiples of m>1 for a wide class of linear numeration systems. As an example, the number of states of the trim minimal automaton accepting the greedy representations of mN in the Fibonacci system is exactly 2m^2. [less ▲]Detailed reference viewed: 143 (37 ULiège) Game over : mathématiques et jeux vidéosRigo, Michel Learning material (2011)Le but de cet exposé est de présenter, à travers plusieurs exemples simples, des outils mathématiques utilisés dans la conception de jeux vidéos (par exemple : projections, produits scalaire et vectoriel ... [more ▼]Le but de cet exposé est de présenter, à travers plusieurs exemples simples, des outils mathématiques utilisés dans la conception de jeux vidéos (par exemple : projections, produits scalaire et vectoriel, calcul matriciel pour l'animation en 3D, fonctions et fractales pour la création de textures procédurales et de matériaux, etc.). Les exemples seront choisis en fonction des connaissances préalables du public (analyse, algèbre, géométrie) et permettront de mettre en évidence l'utilité en infographie des concepts vus au cours de mathématiques. [less ▲]Detailed reference viewed: 502 (50 ULiège) Qui veut jouer avec moi ?Rigo, Michel Learning material (2011)Dans cet exposé accessible au plus grand nombre, nous présentons à travers quelques jeux célèbres (la tablette de chocolat empoisonnée, le jeu de Nim, le jeu de Wythoff, le paradoxe du prisonnier) les ... [more ▼]Dans cet exposé accessible au plus grand nombre, nous présentons à travers quelques jeux célèbres (la tablette de chocolat empoisonnée, le jeu de Nim, le jeu de Wythoff, le paradoxe du prisonnier) les notions de positions gagnante ou perdante et de stratégie. Cela motive l'analyse mathématique d'un jeu. Bien au-delà du simple caractère ludique, nous montrons l'intérêt de la notion de jeu comme modèle dans des domaines aussi variés que l'informatique, la biologie ou encore l'économie mais aussi les interactions existant avec d'autres branches des mathématiques. [less ▲]Detailed reference viewed: 260 (23 ULiège) Syntactic complexity of ultimately periodic sets of integersRigo, Michel ; Vandomme, Elise in Lecture Notes in Computer Science (2011), 6638We compute the cardinality of the syntactic monoid of the language 0^∗rep_b(mN) made of base b expansions of the multiples of the integer m. We also give lower bounds for the syntactic complexity of any ... [more ▼]We compute the cardinality of the syntactic monoid of the language 0^∗rep_b(mN) made of base b expansions of the multiples of the integer m. We also give lower bounds for the syntactic complexity of any (ultimately) periodic set of integers written in base b. We apply our results to some well studied problem: decide whether or not a b-recognizable sets of integers is ultimately periodic. [less ▲]Detailed reference viewed: 103 (27 ULiège)