Scientific conference in universities or research centers (Scientific conferences in universities or research centers)
Binomial^3 : coefficients, equivalence, complexity…
Rigo, Michel
2020
 

Files


Full Text
Rigo.pdf
Author preprint (574.57 kB)
Beamer de la conférence
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
binomial coefficient; nilpotent group; combinatorics on words
Abstract :
[en] The binomial coefficient (x,y) of the words x and y is the number of times y appears as a (scattered) subword of x. This concept has received a lot of attention, e.g., Simon's congruence, Parikh matrices, reconstruction problem, ... A few years ago, we introduced the k-binomial equivalence: Two words u and v are k-binomially equivalent if the binomial coefficients (u,x) and (v,x) agree for all words x of length up to k. This is a refinement of the usual abelian equivalence. First, I will review several results (joint work with P. Salimov, M. Lejeune, J. Leroy, M. Rosenfeld) related to k-binomial complexity (where factors of length n are counted up to k-binomial equivalence) for Sturmian words, Thue-Morse word and Tribonacci word. Then I will concentrate on k-binomial equivalence classes for finite words. In particular, I will discuss the fact that the submonoid generated by the generators of the free nil-2 group on m generators is isomorphic to the quotient of the free monoid {1,...,m}^∗ by the 2-binomial equivalence (joint work with M. Lejeune, M. Rosenfeld).
Disciplines :
Mathematics
Author, co-author :
Rigo, Michel  ;  Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Language :
English
Title :
Binomial^3 : coefficients, equivalence, complexity…
Publication date :
13 July 2020
Event name :
One World Seminar on Combinatorics on Words
Event organizer :
A. Frid, N. Rampersad, J. Shallit, M. Stipulanti
Event date :
13-7-2020
Audience :
International
Available on ORBi :
since 12 July 2020

Statistics


Number of views
79 (5 by ULiège)
Number of downloads
43 (4 by ULiège)

Bibliography


Similar publications



Contact ORBi