Results 1-9 of 9. Search equation: ((author:Waxweiler, author:Laurent)) AND ((filter:inst))   in Mathematics Sort: Title Author Issue date Filter: All documents types Scientific journals - Article - Short communication - Book review - Letter to the editor - Complete issue - OtherBooks - Book published as author, translator, etc. - Collective work published as editor or directorParts of books - Contribution to collective works - Contribution to encyclopedias, dictionaries... - Preface, postface, glossary...Scientific congresses and symposiums - Unpublished conference/Abstract - Paper published in a book - Paper published in a journal - PosterScientific conference in universities or research centersReports - Expert report - Internal report - External report - OtherDissertations and theses - Master of advanced studies dissertation - Master's dissertation - Doctoral thesis - Post doctoral thesisLearning materials - Course notes - OtherPatentCartographic materials - Single work - Part of another publicationComputer developments - Textual, factual or bibliographical database - Software - OtherE-prints/Working papers - First made available on ORBi - Already available on another siteDiverse speeches and writings - Article for general public - Conference given outside the academic context - Speech/Talk - Other     1 Defining multiplication in some additive expansions of polynomial ringsPoint, Françoise; Rigo, Michel ; Waxweiler, Laurentin Communications in Algebra (2016), 44Adapting a result of R. Villemaire on expansions of Presburger arithmetic, we show how to define multiplication in some expansions of the additive reduct of certain Euclidean rings. In particular, this ... [more ▼]Adapting a result of R. Villemaire on expansions of Presburger arithmetic, we show how to define multiplication in some expansions of the additive reduct of certain Euclidean rings. In particular, this applies to polynomial rings over a finite field. [less ▲]Detailed reference viewed: 35 (11 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: 122 (10 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: 139 (19 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: 160 (35 ULiège) Structure of the minimal automaton of a numeration languageCharlier, Emilie ; Rampersad, Narad ; Rigo, Michel et alin 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: 127 (20 ULiège) State complexity of testing divisibilityCharlier, Emilie ; Rampersad, Narad ; Rigo, Michel et alin 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: 90 (19 ULiège) Structure of the minimal automaton of a numeration language and applications to state complexityCharlier, Emilie ; Rampersad, Narad ; Rigo, Michel et alin 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: 71 (8 ULiège) Caractère reconnaissable d'ensembles de polynômes à coefficients dans un corps finiWaxweiler, Laurent Doctoral thesis (2009)Nous nous plaçons dans le cadre de l'anneau des polynômes sur un corps fini. Si P est un polynôme de degré au moins 1, tout polynôme Q se décompose de manière unique sous la forme d'une combinaison ... [more ▼]Nous nous plaçons dans le cadre de l'anneau des polynômes sur un corps fini. Si P est un polynôme de degré au moins 1, tout polynôme Q se décompose de manière unique sous la forme d'une combinaison linéaire de puissances de P, dont les coefficients sont des polynômes dont le degré est strictement inférieur à celui de P. À une telle décomposition, nous associons un mot que nous appelons la P-représentation du polynôme Q. Un ensemble de polynômes est alors qualifié de P-reconnaissable si il existe un automate fini déterministe qui accepte l'ensemble des P-représentations de ses éléments. Dans cette thèse, nous montrons que les ensembles P-reconnaissables sont exactement ceux qui sont définissables par une formule du premier ordre dans une certaine structure S(P) basée sur un prédicat dépendant du polynôme P. Nous donnons aussi une caractérisation des ensembles P-reconnaissables en terme de suites P-automatiques. Nous apportons également une réponse partielle à la question de savoir quels sont les ensembles reconnaissables simultanément dans toutes les bases de degré au moins 1. Finalement, nous montrons que si P et Q sont deux polynômes de degré au moins 1 et multiplicativement indépendants, alors la multiplication est définissable dans la réunion des structures S(P) et S(Q). [less ▲]Detailed reference viewed: 219 (19 ULiège) A note on syndeticity, recognizable sets and Cobham's theoremRigo, Michel ; Waxweiler, Laurent in Bulletin of the European Association for Theoretical Computer Science (2006), 88In this note, we give an alternative proof of the following result. Let p,q>=2 be two multiplicatively independent integers. If an infinite set of integers is both p- and q-recognizable, then it is ... [more ▼]In this note, we give an alternative proof of the following result. Let p,q>=2 be two multiplicatively independent integers. If an infinite set of integers is both p- and q-recognizable, then it is syndetic. Notice that this result is needed in the classical proof of the celebrated Cobham’s theorem. Therefore the aim of this paper is to complete [13] and [1] to obtain an accessible proof of Cobham’s theorem. [less ▲]Detailed reference viewed: 25 (2 ULiège) 1