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 1 to 20 of 111 1 2 3 4 5 6     On Cobham's theoremDurand, Fabien; Rigo, Michel in Handbook of Automata (in press)Let k >= 2 be an integer. A set X of integers is k-recognizable if the language of k-ary representations of the elements in X is accepted by a finite automaton. The celebrated theorem of Cobham from 1969 ... [more ▼]Let k >= 2 be an integer. A set X of integers is k-recognizable if the language of k-ary representations of the elements in X is accepted by a finite automaton. The celebrated theorem of Cobham from 1969 states that if a set of integers is both k-recognizable and ℓ-recognizable, then it is a finite union of arithmetic progressions. We present several extensions of this result to nonstandard numeration systems, we describe the relationships with substitutive and automatic words and list Cobham-type results in various contexts. [less ▲]Detailed reference viewed: 166 (25 ULg) Advanced graph theory and combinatoricsRigo, Michel Book published by ISTE-John Wiley & Sons (2017)This book focuses on some of the main notions arising in graph theory, with an emphasis throughout on the possible applications of the theory and the fruitful links that exist with linear algebra ... [more ▼]This book focuses on some of the main notions arising in graph theory, with an emphasis throughout on the possible applications of the theory and the fruitful links that exist with linear algebra. Commencing with basic notions such as connectedness, Eulerian, Hamiltonian and planar graphs, opens the way for a variety of applications. A short chapter is devoted to complexity theory, and after a presentation of the chromatic polynomial and Ramsey numbers, the book highlights the important interplay between graph theory and linear algebra. Perron-Frobenius theory is then presented. With rational generating functions and powers of the adjacency matrix, counting walks in a directed multigraph is a recurrent topic of the book and is studied in great detail. Google’s PageRank is then covered in the final chapter of the book. Every application of the theory is accompanied by fully worked examples and proofs, and supplemented by over 100 exercises throughout the book. This allows the student to gain a full and thorough understanding of advanced graph theory and its potential applications. [less ▲]Detailed reference viewed: 29 (2 ULg) Coefficients binomiaux de motsRigo, Michel Scientific conference (2016, September 15)Le coefficient binomial (u,v) de deux mots u et v est défini comme le nombre de fois que v apparaît comme sous-suite du mot u. Par exemple, (abbab,ab)=4. Il étend de manière naturelle le coefficient ... [more ▼]Le coefficient binomial (u,v) de deux mots u et v est défini comme le nombre de fois que v apparaît comme sous-suite du mot u. Par exemple, (abbab,ab)=4. Il étend de manière naturelle le coefficient binomial de deux entiers. Ce concept a été largement étudié depuis plus d'une trentaine d'années (cf. par exemple, Simon et Sakarovitch). Dans cet exposé, je passerai tout d'abord en revue quelques résultats combinatoires classiques pour ensuite m'attarder sur l'équivalence k-binomiale. A l'instar de l'équivalence k-abélienne étudiée par Karhumäki et al., deux mots x et y sont k-binomialement équivalents si leurs coefficients binomiaux (x,v) et (y,v) coïncident pour les mots v de longueur au plus k. En fin d'exposé, j'évoquerai l'extension récente des triangles de Pascal et de Sierpinski à ces coefficients. [less ▲]Detailed reference viewed: 13 (2 ULg) Dobble, analyse d'un jeu de cartesRigo, Michel Conference given outside the academic context (2016)Detailed reference viewed: 41 (2 ULg) Asymptotic properties of free monoid morphismsCharlier, Emilie ; Leroy, Julien ; Rigo, Michel in Linear Algebra & its Applications (2016), 500Detailed reference viewed: 20 (9 ULg) Dix ans de Maths à Modeler à Liège'' ou comment un enseignant/chercheur s'invite dans des classes du secondaireRigo, Michel Conference given outside the academic context (2016)Les missions d'un professeur d'université sont multiples : recherche, enseignement mais aussi citoyenneté. Depuis une dizaine d'années, je réalise de multiples activités de sensibilisation aux ... [more ▼]Les missions d'un professeur d'université sont multiples : recherche, enseignement mais aussi citoyenneté. Depuis une dizaine d'années, je réalise de multiples activités de sensibilisation aux mathématiques : exposés, activités ludiques en petits groupes, etc. En répondant modestement à la question : "les maths ça sert à quoi ?", le but recherché est de démontrer l'utilité souvent méconnue des mathématiques, et de la recherche dans ce domaine (Google, réseaux sociaux, jeux vidéos, magie, etc.). Dans cette présentation, je dresserai tout d'abord l'historique du projet et tenterai d'analyser les actions menées. Ensuite, l'auditoire assistera à un tour de mathémagie et participera, de façon interactive, à un jeu démontrant l'importance du concept de preuve en mathématique. Ces jeux sont tirés de "Situations-Recherche pour la classe" développées par des chercheurs grenoblois. Enfin, j'expliquerai comment des étudiants de l'ULg (bacheliers, masters, étudiants à l'agrégation) et des doctorants participent à cette action. [less ▲]Detailed reference viewed: 28 (2 ULg) Non-homogeneous Beatty sequences leading to invariant gamesCassaigne, Julien; Duchêne, Eric; Rigo, Michel in SIAM Journal on Discrete Mathematics (2016), 30We characterize pairs of complementary non-homogeneous Beatty sequences $(A_n)_{n>0}$ and $(B_n)_{n>0}$, with the restriction $A_1=1$ and $B_1\geq 3$, for which there exists an invariant take-away game ... [more ▼]We characterize pairs of complementary non-homogeneous Beatty sequences $(A_n)_{n>0}$ and $(B_n)_{n>0}$, with the restriction $A_1=1$ and $B_1\geq 3$, for which there exists an invariant take-away game having $\{(A_n,B_n),(B_n,A_n)\mid n> 0\}\cup\{(0,0)\}$ as set of $P$-positions. Using the notion of Sturmian word arising in combinatorics on words, this characterization can be translated into a decision procedure relying only on a few algebraic tests about algebraicity or rational independence. This work partially answers to a question of Larsson et al. raised in Larsson et al. [less ▲]Detailed reference viewed: 16 (1 ULg) Generalized Pascal triangle for binomial coefficients of wordsLeroy, Julien ; Rigo, Michel ; Stipulanti, Manon in Advances in Applied Mathematics (2016), 80We introduce a generalization of Pascal triangle based on binomial coefficients of finite words. These coefficients count the number of times a word appears as a subsequence of another finite word ... [more ▼]We introduce a generalization of Pascal triangle based on binomial coefficients of finite words. These coefficients count the number of times a word appears as a subsequence of another finite word. Similarly to the Sierpiński gasket that can be built as the limit set, for the Hausdorff distance, of a convergent sequence of normalized compact blocks extracted from Pascal triangle modulo 2, we describe and study the first properties of the subset of [0, 1] × [0, 1] associated with this extended Pascal triangle modulo a prime p. [less ▲]Detailed reference viewed: 83 (50 ULg) 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: 25 (9 ULg) Combinatorics, Words and Symbolic DynamicsBerthé, Valérie; Rigo, Michel Book published by Cambridge University Press (2016)Internationally recognised researchers look at developing trends in combinatorics with applications in the study of words and in symbolic dynamics. They explain the important concepts, providing a clear ... [more ▼]Internationally recognised researchers look at developing trends in combinatorics with applications in the study of words and in symbolic dynamics. They explain the important concepts, providing a clear exposition of some recent results, and emphasise the emerging connections between these different fields. Topics include combinatorics on words, pattern avoidance, graph theory, tilings and theory of computation, multidimensional subshifts, discrete dynamical systems, ergodic theory, numeration systems, dynamical arithmetics, automata theory and synchronised words, analytic combinatorics, continued fractions and probabilistic models. Each topic is presented in a way that links it to the main themes, but then they are also extended to repetitions in words, similarity relations, cellular automata, friezes and Dynkin diagrams. The book will appeal to graduate students, research mathematicians and computer scientists working in combinatorics, theory of computation, number theory, symbolic dynamics, tilings and stringology. It will also interest biologists using text algorithms. [less ▲]Detailed reference viewed: 28 (1 ULg) Jouer avec les mots, pourquoi et comment ?Rigo, Michel Learning material (2016)Ce texte reprend l'essentiel de ma présentation à la Brussels Math. Summer School du 4 août 2015. Il s'agit d'une courte introduction à la combinatoire des mots. A l'instar de Raymond Queneau et ses cent ... [more ▼]Ce texte reprend l'essentiel de ma présentation à la Brussels Math. Summer School du 4 août 2015. Il s'agit d'une courte introduction à la combinatoire des mots. A l'instar de Raymond Queneau et ses cent mille milliards de poèmes, nous construisons des suites aux propriétés surprenantes. Pour ne pas allonger le texte, nous avons décidé d'éviter l'emploi d'automates finis. Les premiers résultats en combinatoire des mots remontent au début du siècle précédent, avec les travaux du mathématicien norvégien Axel Thue. Cette branche des mathématiques étudie la structure et les arrangements apparaissant au sein de suites finies, ou infinies, de symboles appartenant à un ensemble fini. Un carré est la juxtaposition de deux répétitions d'un même mot. On dira qu'un mot comme `taratata' contient un carré. Il est aisé de vérifier que, si on dispose uniquement de deux symboles, alors tout mot de longueur au moins 4 contient un carré. Cette observation amène de nombreuses questions simples à formuler : Avec trois symboles, peut-on construire un mot arbitrairement long ne contenant pas de carré ? Si on se limite à deux symboles, peut-on construire un mot arbitrairement long sans cube, i.e., évitant la juxtaposition de trois répétitions d'un même mot ? En fonction de la taille de l'alphabet, quels motifs doivent nécessairement apparaître et quels sont ceux qui sont évitables ? Que se passe-t-il si on autorise certaines permutations ? [less ▲]Detailed reference viewed: 41 (2 ULg) Computing k-binomial equivalence and avoiding binomial repetitionsRigo, Michel Conference (2015, October 28)In this talk, I will first recall basic results on binomial coefficients of words, then review the connections and differences with Parikh matrices. As a generalization of abelian equivalence, two words u ... [more ▼]In this talk, I will first recall basic results on binomial coefficients of words, then review the connections and differences with Parikh matrices. As a generalization of abelian equivalence, two words u and v are k-binomially equivalent if every word of length at most k appears as a subword of u exactly as many times as it appears as a subword of v. So a k-binomial square is a word uv where u and v are k-binomially equivalent. We will discuss avoidance of squares and cubes in infinite words (this is a joint word with M. Rao). Finally, I will consider the question of deciding whether or not two finite words are k-binomially equivalent. This problem has recently been shown to be decidable in polynomial time by Freydenberger, Gawrychowski et al. [less ▲]Detailed reference viewed: 49 (8 ULg) Use of the wavelet theory as a tool to investigate the l-abelian complexity of a sequenceKleyntssens, Thomas ; Nicolay, Samuel ; Vandomme, Elise et alPoster (2015, September 23)The concept of k-automatic sequences is at the intersection of number theory and formal language theory. It has been generalized by the notion of k-regularity that allows to study sequences with values in ... [more ▼]The concept of k-automatic sequences is at the intersection of number theory and formal language theory. It has been generalized by the notion of k-regularity that allows to study sequences with values in a (possibly infinite) ring. This concept provides us with structural information about how the different terms of the sequence are related to each other. They are many different notions related to the measure of complexity of an infinite sequence w. A classical approach is its factor complexity. In an abelian context, the analogue to the factor complexity is the abelian complexity where the number of distinct factors of length n is counted up to abelian equivalence. The notion of abelian complexity was extended to that of l-abelian complexity. In this talk, I propose to use tools from the wavelet theory to analyze the l-abelian complexity. For the numerical simulations, I apply the wavelet leaders method that allows to study the pointwise regularity of signals. [less ▲]Detailed reference viewed: 24 (8 ULg) Jouer avec les mots, pourquoi et comment ?Rigo, Michel Scientific conference (2015, August 04)A l'instar de Raymond Queneau et ses cent mille milliards de poèmes, cet exposé a pour but de compter et de construire des mots aux propriétés parfois surprenantes. Les premiers résultats en combinatoire ... [more ▼]A l'instar de Raymond Queneau et ses cent mille milliards de poèmes, cet exposé a pour but de compter et de construire des mots aux propriétés parfois surprenantes. Les premiers résultats en combinatoire des mots remontent au début du siècle précédent, avec les travaux du mathématicien norvégien Axel Thue. Cette branche des mathématiques étudie la structure et les arrangements apparaissant au sein de suites finies, ou infinies, de symboles appartenant à un ensemble fini. Donnons un exemple rudimentaire. Un carré est la juxtaposition de deux répétitions d'un mot, ainsi "coco" ou "bonbon" sont des carrés. On dira alors qu'un mot comme "taratata" contient un carré. Il est aisé de vérifier que, si on dispose uniquement de deux symboles "a" et "b", alors tout mot de longueur au moins 4 contient un des carrés "aa", "bb", "abab" ou encore "baba". On dira donc que, sur deux symboles, les carrés sont inévitables. Cette observation pose des questions intéressantes et simples à formuler : Avec trois symboles, peut-on construire un mot arbitrairement long ne contenant pas de carré ? Si on se limite à deux symboles, peut-on construire un mot arbitrairement long sans cube, i.e., évitant la juxtaposition de trois répétitions d'un même mot ? En fonction de la taille de l'alphabet, quels motifs doivent nécessairement apparaître et quels sont ceux qui sont évitables ? Que se passe-t-il si on autorise certaines permutations ? etc. Dans cet exposé, on passera en revue quelques constructions simples de mots finis ou infinis : mot de Thue-Morse, mot de Fibonacci, mots Sturmiens. Nous montrerons aussi que les applications sont nombreuses : arithmétique, transcendance en théorie des nombres, informatique mathématique et théorie des automates, pavages du plan, dynamique symbolique et codage de rotations, infographie, géométrie discrète et représentation de segment de droites à l'écran, bio-informatique, ... [less ▲]Detailed reference viewed: 76 (9 ULg) Is Büchi's theorem useful for you?Rigo, Michel Conference (2015, May 28)Almost a century ago, Presburger showed that the first order theory of the natural numbers with addition is decidable. Following the work of Büchi in 1960, this result still holds when adding a function ... [more ▼]Almost a century ago, Presburger showed that the first order theory of the natural numbers with addition is decidable. Following the work of Büchi in 1960, this result still holds when adding a function $V_k$ to the structure, where $V_k(n)$ is the largest power of $k\ge 2$ diving $n$. In particular, this leads to a logical characterization of the $k$-automatic sequences. During the last few years, many applications of this result have been considered in combinatorics on words, mostly by J. Shallit and his coauthors. In this talk, we will present this theorem of Büchi where decidability relies on finite automata.Then we will review some results about automatic sequences or morphic words that can be proved automatically (i.e., the proof is carried on by an algorithm). Finally, we will sketch the limitation of this technique. With a single line formula, one can prove automatically that the Thue-Morse word has no overlap but, hopefully, not all the combinatorial properties of morphic words can be derived in this way. [less ▲]Detailed reference viewed: 53 (5 ULg) Invariant games and non-homogeneous Beatty sequencesRigo, Michel Scientific conference (2015, January 08)The aim of this talk is to introduce some notions arising in combinatorial game theory and make the connection with combinatorics on words. We characterize all pairs of complementary non-homogenous Beatty ... [more ▼]The aim of this talk is to introduce some notions arising in combinatorial game theory and make the connection with combinatorics on words. We characterize all pairs of complementary non-homogenous Beatty sequences (A_n)n≥0 and (B_n)n≥0 for which there exists an invariant game having exactly {(A_n,B_n)∣n≥0}∪{(B_n,A_n)∣n≥0} as set of P-positions. Using the notion of Sturmian word and tools arising in symbolic dynamics and combinatorics on words, this characterization can be translated to a decision procedure relying only on a few algebraic tests about algebraicity or rational independence. Given any four real numbers defining the two sequences, up to these tests, we can therefore decide whether or not such an invariant game exists. [less ▲]Detailed reference viewed: 21 (5 ULg) Another Generalization of Abelian Equivalence: Binomial Complexity of Infinite Words (long version)Rigo, Michel ; Salimov, Pavelin Theoretical Computer Science (2015), 601The binomial coefficient of two words $u$ and $v$ is the number of times $v$ occurs as a subsequence of $u$. Based on this classical notion, we introduce the $m$-binomial equivalence of two words refining ... [more ▼]The binomial coefficient of two words $u$ and $v$ is the number of times $v$ occurs as a subsequence of $u$. Based on this classical notion, we introduce the $m$-binomial equivalence of two words refining the abelian equivalence. Two words $x$ and $y$ are $m$-binomially equivalent, if, for all words $v$ of length at most $m$, the binomial coefficients of $x$ and $v$ and respectively, $y$ and $v$ are equal. The $m$-binomial complexity of an infinite word $x$ maps an integer $n$ to the number of $m$-binomial equivalence classes of factors of length $n$ occurring in $x$. We study the first properties of $m$-binomial equivalence. We compute the $m$-binomial complexity of two classes of words: Sturmian words and (pure) morphic words that are fixed points of Parikh-constant morphisms like the Thue--Morse word, i.e., images by the morphism of all the letters have the same Parikh vector. We prove that the frequency of each symbol of an infinite recurrent word with bounded $2$-binomial complexity is rational. [less ▲]Detailed reference viewed: 32 (3 ULg) An analogue of Cobham's theorem for graph directed iterated function systemsCharlier, Emilie ; Leroy, Julien ; Rigo, Michel in Advances in Mathematics (2015), 280Feng and Wang showed that two homogeneous iterated function systems in $\mathbb{R}$ with multiplicatively independent contraction ratios necessarily have different attractors. In this paper, we extend ... [more ▼]Feng and Wang showed that two homogeneous iterated function systems in $\mathbb{R}$ with multiplicatively independent contraction ratios necessarily have different attractors. In this paper, we extend this result to graph directed iterated function systems in $\mathbb{R}^n$ with contraction ratios that are of the form $\frac{1}{\beta}$, for integers $\beta$. By using a result of Boigelot {\em et al.}, this allows us to give a proof of a conjecture of Adamczewski and Bell. In doing so, we link the graph directed iterated function systems to Büchi automata. In particular, this link extends to real numbers $\beta$. We introduce a logical formalism that permits to characterize sets of $\mathbb{R}^n$ whose representations in base $\beta$ are recognized by some Büchi automata. This result depends on the algebraic properties of the base: $\beta$ being a Pisot or a Parry number. The main motivation of this work is to draw a general picture representing the different frameworks where an analogue of Cobham's theorem is known. [less ▲]Detailed reference viewed: 42 (19 ULg) Avoiding 2-binomial squares and cubesRao, Michaël; Rigo, Michel ; Salimov, Pavelin Theoretical Computer Science (2015), 572Two finite words $u,v$ are $2$-binomially equivalent if, for all words $x$ of length at most $2$, the number of occurrences of $x$ as a (scattered) subword of $u$ is equal to the number of occurrences of ... [more ▼]Two finite words $u,v$ are $2$-binomially equivalent if, for all words $x$ of length at most $2$, the number of occurrences of $x$ as a (scattered) subword of $u$ is equal to the number of occurrences of $x$ in $v$. This notion is a refinement of the usual abelian equivalence. A $2$-binomial square is a word $uv$ where $u$ and $v$ are $2$-binomially equivalent. In this paper, considering pure morphic words, we prove that $2$-binomial squares (resp. cubes) are avoidable over a $3$-letter (resp. $2$-letter) alphabet. The sizes of the alphabets are optimal. [less ▲]Detailed reference viewed: 18 (7 ULg) A New Approach to the 2-Regularity of the ℓ-Abelian Complexity of 2-Automatic SequencesParreau, Aline; Rigo, Michel ; Rowland, Eric et alin The Electronic Journal of Combinatorics (2015), 22(1), 127We prove that a sequence satisfying a certain symmetry property is 2-regular in the sense of Allouche and Shallit, i.e., the Z-module generated by its 2-kernel is finitely generated. We apply this theorem ... [more ▼]We prove that a sequence satisfying a certain symmetry property is 2-regular in the sense of Allouche and Shallit, i.e., the Z-module generated by its 2-kernel is finitely generated. We apply this theorem to develop a general approach for studying the l-abelian complexity of 2-automatic sequences. In particular, we prove that the period-doubling word and the Thue--Morse word have 2-abelian complexity sequences that are 2-regular. Along the way, we also prove that the 2-block codings of these two words have 1-abelian complexity sequences that are 2-regular. [less ▲]Detailed reference viewed: 50 (16 ULg)