Browse ORBi by ORBi project

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

Extensions and restrictions of Wythoff's game preserving its P-positions Rigo, 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: 66 (7 ULg)Syntactic complexity of ultimately periodic sets of integers Rigo, 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: 17 (3 ULg)Defining multiplication for polynomials over a finite field. Rigo, Michel ; E-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: 95 (6 ULg)Logical characterization of recognizable sets of polynomials over a finite field Rigo, Michel ; in International Journal of Foundations of Computer Science (2011), 22(7), 1549-1563 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 ... [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: 123 (14 ULg)The minimal automaton recognizing mN in a linear numeration system Charlier, Emilie ; Rampersad, Narad ; Rigo, Michel et al in Integers: Electronic Journal of Combinatorial Number Theory (2011), 11B(A4), 1-24 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 ... [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: 134 (31 ULg)Game over : mathématiques et jeux vidéos Rigo, 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: 435 (44 ULg)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: 233 (23 ULg)Syntactic complexity of ultimately periodic sets of integers Rigo, Michel ; Vandomme, Elise in Lecture Notes in Computer Science (2011), 6638 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: 97 (26 ULg)Representing real numbers in a generalized numeration system Charlier, Emilie ; ; Rigo, Michel in Journal of Computer & System Sciences (2011), 77 We show how to represent an interval of real numbers in an abstract numeration system built on a language that is not necessarily regular. As an application, we consider representations of real numbers ... [more ▼] We show how to represent an interval of real numbers in an abstract numeration system built on a language that is not necessarily regular. As an application, we consider representations of real numbers using the Dyck language. We also show that our framework can be applied to the rational base numeration systems. [less ▲] Detailed reference viewed: 95 (23 ULg)Arithmétique, Automates et Géométrie discrète ; Rigo, Michel Diverse speeche and writing (2011) cours au Collège Belgique Detailed reference viewed: 58 (9 ULg)State complexity of testing divisibility Charlier, Emilie ; Rampersad, Narad ; Rigo, Michel et al in McQuillan, Ian, Pighizzini, Giovanni (Ed.) Proceedings Twelfth Annual Workshop on Descriptional Complexity of Formal Systems (2010, August) Under some mild assumptions, we study the state complexity of the trim minimal automaton accepting the greedy representations of the multiples of m>=2 for a wide class of linear numeration systems. As an ... [more ▼] Under some mild assumptions, we study the state complexity of the trim minimal automaton accepting the greedy representations of the multiples of m>=2 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: 76 (19 ULg)Structure of the minimal automaton of a numeration language Charlier, Emilie ; Rampersad, Narad ; Rigo, Michel et al in Actes de LaCIM 2010 (2010, August) 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 ... [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. [less ▲] Detailed reference viewed: 102 (20 ULg)Invariant games ; Rigo, Michel in Theoretical Computer Science (2010), 411 In the context of 2-player removal games, we define the notion of invariant game for which each allowed move is independent of the position it is played from. We present a family of invariant games which ... [more ▼] In the context of 2-player removal games, we define the notion of invariant game for which each allowed move is independent of the position it is played from. We present a family of invariant games which are variations of Wythoff's game. The set of P-positions of these games are given by a pair of complementary Beatty sequences related to the irrational quadratic number $\alpha_k = (1; \overline{1, k})$. We also provide a recursive characterization of this set. [less ▲] Detailed reference viewed: 73 (30 ULg)Systèmes de numération abstraits et combinatoire des mots (habilitation à diriger des recherches) Rigo, Michel Post doctoral thesis (2010) We summary the main properties of abstract numeration systems and their links to combinatorics on words and combinatorial game theory. Detailed reference viewed: 137 (34 ULg)Extensions and restrictions of Wythoff's game preserving its P positions ; ; et al in Journal of Combinatorial Theory - Series A (2010), 117 We consider extensions and restrictions of Wythoff's game having exactly the same set of P positions as the original game. No strict subset of rules give the same set of P positions. On the other hand, we ... [more ▼] We consider extensions and restrictions of Wythoff's game having exactly the same set of P positions as the original game. No strict subset of rules give 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 doable in polynomial time. Many arguments rely on the infinite Fibonacci word, automatic sequences and the corresponding number system. With these tools, we provide new two-dimensional morphisms generating an infinite picture encoding respectively P positions of Wythoff's game and moves that can be adjoined. [less ▲] Detailed reference viewed: 73 (16 ULg)Special issue dedicated to the twelfth "Journées montoises d'informatique théorique" ; Rigo, Michel in RAIRO : Informatique Théorique et Applications = Theoretical Informatics and Applications (2010), 44(1), 1-192 Detailed reference viewed: 17 (3 ULg)Special issue dedicated to the second "AutoMathA conference" ; ; et al in Discrete Mathematics & Theoretical Computer Science (2010), 12 Detailed reference viewed: 10 (0 ULg)Structure of the minimal automaton of a numeration language and applications to state complexity Charlier, Emilie ; Rampersad, Narad ; Rigo, Michel et al in Actes des Journées Montoises d'Informatique Théorique (2010) 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 ... [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 > 1, there is a morphism mapping A onto the automaton arising from the Bertrand system associated with the number . Under some mild assumptions, we also study the state complexity of the trim minimal automaton accepting the greedy representations of the multiples of m>=2 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: 56 (7 ULg)Multidimensional generalized automatic sequences and shape-symmetric morphic words Charlier, Emilie ; ; Rigo, Michel in Discrete Mathematics (2010), 310 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 numeration system S. In this paper, we consider an ... [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 numeration system S. In this paper, we consider an analogous definition in a multidimensional setting and study its relation to the shapesymmetric infinite words introduced by Arnaud Maes. More precisely, for d>1, we show that a multidimensional infinite word x 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: 59 (16 ULg)On the Recognizability of Self-Generating Sets ; Lacroix, Anne ; Rigo, Michel in Journal of Integer Sequences (2010), 13 Let I be a finite set of integers and F be a finite set of maps of the form n->k_i n + l_i with integer coefficients. For an integer base k>=2, we study the k-recognizability of the minimal set X of ... [more ▼] Let I be a finite set of integers and F be a finite set of maps of the form n->k_i n + l_i with integer coefficients. For an integer base k>=2, we study the k-recognizability of the minimal set X of integers containing I and satisfying f(X)\subseteq X for all f in F. In particular, solving a conjecture of Allouche, Shallit and Skordev, we show under some technical conditions that if two of the constants k_i are multiplicatively independent, then X is not k-recognizable for any k>=2. [less ▲] Detailed reference viewed: 31 (9 ULg) |
||