April 27th:
Louis Lemonnier,
Applied string diagram rewriting,
slides.
Abstract: Monads in category theory are algebraic
structures that can be used to model computational effects in
programming languages. We show how the notion of "centre", and
more generally "centrality", may be formulated for strong monads
acting on symmetric monoidal categories. We identify three
equivalent conditions which characterise the existence of the
centre of a strong monad (some of which relate it to the
premonoidal centre of Power and Robinson) and we show that every
strong monad on many well-known naturally occurring categories
does admit a centre, thereby showing that this new notion is
ubiquitous. More generally, we study central submonads, which are
necessarily commutative, just like the centre of a strong
monad. We provide a computational interpretation for our ideas by
formulating equational theories of lambda calculi equipped with
central submonads, we describe categorical models for these
theories and prove soundness, completeness and internal language
results for our categorical semantics.
March 30th:
Titouan Carette,
Applied string diagram rewriting,
slides.
Abstract: The last decade has seen many diagrammatical
languages being developed. Those can be seen as algebraic
axiomatisations of monoidal categories via generators and
equations. However, the string diagrammatic notations and a few
tricks allow us to present them as graphs together with rewriting
rules without mentioning the category-theoretic definition. Such a
presentation simplifies the outreach of those diagrammatical methods
beyond category theorists and the concrete implementation of
diagram-based software. In this talk, I will present the general
formalism of equational theories for props and some of the technics,
with a focus on flexsymmetry, allowing to reduce string diagrams to
simple graphs. Then, I will describe in more detail two examples of
such diagrammatical languages: Graphical Linear Algebra and
ZW-calculus. I will show how combining those languages with graph
rewriting provides algorithms for various problems: solving linear
equations, counting perfect matching, computing determinants and
inversing matrices.
Fall 2022
February 16th:
Ricardo Guilherme,
Quasi-crystals for arbitrary root systems: A
generalization of the hypoplactic monoid and a Littelmann path
model,
slides.
Abstract: The plactic monoid, formally introduced by
Lascoux and Schützenberger, can be obtained by identifying words in
the same position of isomorphic connected components of a Kashiwara
crystal of Cartan type A. This method enriched the structure of the
plactic monoid and allowed its generalization, because the
construction still results in a monoid for other crystals of another
type. Although introduced in an independent work, the Littelmann
path model over a root system yields a crystal structure, which
allows it to be considered as a realization for seminormal
crystals. In this talk, following joint work with Alan Cain and
António Malheiro, we show that the hypoplactic monoid, introduced by
Krob and Thibon, admits an analogous approach. For this purpose, we
introduce the notion of quasi-crystal associated to a root system
and the notion of quasi-tensor product of quasi-crystals. We show
that a quasi-crystal gives rise to a weight labelled graph, called
quasi-crystal graph, which for the class of seminormal
quasi-crystals results in a one-to-one correspondence. In this
framework, we show that the hypoplactic monoid can be obtained by
identifying words in the same position of isomorphic connected
components of a quasi-crystal of type A, which leads to its
generalization, because this construction still results in a monoid
for quasi-crystals of another type. We then present some results for
the hypoplactic monoid obtained from a quasi-crystal of type C. We
finally show that the Littelmann path model over a root system
yields a quasi-crystal structure, which makes it a quasi-crystal
monoid.
December 1st:
Mariane Youssef,
Coherence by decreasingness for monoids,
slides.
Abstract: The coherence property studied in string
rewriting systems forms the first step in the computation of a free
resolution of the monoids presented by these systems. In 1987,
Squier demonstrated a method for extending a convergent presentation
of a monoid into a coherent presentation of that monoid by adding a
confluence diagram to each critical pair. On the other hand, van
Oostrom decreasingness theory was introduced in 1994 to study the
confluence property for abstract rewriting systems. This theory
gives a method to investigate the coherence property of abstract
rewriting systems by studying the rewriting steps via a well-founded
labelling on these rewriting steps. This will give a structure of
the proofs by working by induction on the well-founded order defined
on the set of labels. In this talk, I will first briefly introduce
the decreasingness theory of van Oostrom in one-dimensional
polygraphs. I will give a generalization of Squier’s coherence
theorem by a decreasingness approach based on normal forms modulo
cycles, called recurrent forms. Secondly, I will apply this result
to string rewriting systems by developing an example on the braid
monoid on three strands. Finally, I will apply this result on string
rewriting systems endowed with a crystal structure by developing an
example on plactic monoids.
November 10th:
Duarte Ribeiro,
Identities and bases in hypoplactic, sylvester,
Baxter and stylic monoids,
slides.
Abstract: The ubiquitous plactic monoid,
also known as the monoid of Young tableaux, has deep connections to
several areas of mathematics, in particular, to the theory of
symmetric functions. An actively-studied problem is the identities
satisfied by the plactic monoids of finite rank, which are known to
satisfy non-trivial identities but no “global" identity which is
satisfied regardless of rank. In contrast, monoids related to the
plactic monoid, such as the hypoplactic monoid (the monoid of
quasi-ribbon tableaux, connected with quasisymmetric functions),
sylvester monoid (the monoid of binary search trees) and Baxter monoid
(the monoid of pairs of twin binary search trees, connected with
Baxter permutations), satisfy global identities, and the shortest
identities have been characterized. On the other hand, the stylic
monoid, a finite J-trivial quotient of the plactic monoid, shows
promising connections to the well-studied problem of Simon’s
congruence. This talk will focus on results on the hypoplactic
monoid and on the sylvester and Baxter monoids, obtained in joint
work with Alan Cain and António Malheiro (FCT NOVA). We show how
to embed these monoids of higher rank into a direct product of
copies of the corresponding monoid of rank 2. As such, we show
that these monoids satisfy exactly the same identities, for which
we give a full description. Furthermore, we show that the identity
checking problem for these monoids is decidable in polynomial
time. Then, we show that the varieties generated by these monoids
have finite axiomatic rank, and give finite bases for their
equational theories. Finally, we also talk about recent results on
the stylic monoid, obtained in joint work with Thomas Aird
(University of Manchester). We show that these monoids satisfy the
same identities as monoids of upper unitriangular tropical
matrices, and therefore generate the pseudovarieties J_n in
Simon’s hierarchy of J-trivial monoids.
October 27th:
Cyrille Chenavier,
Computation of Koszul homology and application to
involutivity of partial differential systems,
slides.
Abstract: The formal integrability of systems of partial
differential equations plays a fundamental role in different
analysis and synthesis problems for both linear and nonlinear
differential control systems. Following Spencer's theory, to test
the formal integrability of a system of partial differential
equations, we must study when the symbol of the system, namely, the
top-order part of the linearization of the system, is 2-acyclic or
involutive, ie, when certain Spencer cohomology groups
vanish. Combining the fact that Spencer cohomology is dual to Koszul
homology and symbolic computation methods, we show how to
effectively compute the homology modules defined by the Koszul
complex of a finitely presented module over a commutative polynomial
ring. These results are implemented using the OreMorphisms
package. We then use these results to effectively characterize
2-acyclicity and involutivity of the symbol of a linear system of
partial differential equations. Finally, we show explicit
computations on standard examples.
Spring 2022
June 9th:
Nohra Hage,
Super plactic structures: combinatorial and
rewriting approaches,
slides.
Abstract:
We study the super plactic monoid of type A, which is related to
the representations of the general linear Lie superalgebra, by
combinatorial and rewriting methods. We introduce a super version
of the Schützenberger's jeu de taquin on super Young tableaux over
a signed alphabet. We show that this procedure which transforms
super skew tableaux into super Young tableaux is confluent and it
is compatible with the super plactic congruence. We deduce
properties relating the super jeu de taquin to insertion
algorithms on super tableaux. Moreover, we introduce a super
version of the Robinson-Schensted-Knuth correspondence for super
tableaux and we give a combinatorial version of the super
Littlewood-Richardson rule. Finally, we show how the super-plactic
monoid of type A can be studied by a rewriting-approach.
April 21st:
Thibaut Verron,
Signature Gröbner bases and cofactor computation in the free algebra,
slides.
Abstract:
Gröbner bases are a fundamental tool for solving systems of
polynomial equations, and performing arithmetic operations on
ideals. The most recent generation of algorithms computing Gröbner
bases are computing bases with so-called signatures. Those
signatures have proved to be useful far beyond their initial
purpose of eliminating reductions to zero: they also allow to
certify the results of a Gröbner basis computation, by
reconstructing coordinates of the basis elements, as well as
computing syzygies.
In the non-commutative case, Gröbner bases are used for evaluating
formulas in abstract algebra. A signature Gröbner basis of the
ideal, in addition to answering the question, would also give
sufficient data to reconstruct a proof of the computed
implications.
In this talk, we present signature Gröbner basis algorithms for
pure non-commutative polynomials, in the free algebra, and we show
that those algorithms can be used to reconstruct cofactors and
syzygies like in the commutative case.
A common difficulty with non-commutative Gröbner bases is that the
algorithms do not in general terminate. We show how signatures
allow to work around an obstruction to termination, and we
conjecture a characterization of ideals with a finite signature
Gröbner basis.
(Joint work with Clemens Hofstadler).
Fall 2021
December 6th:
Simone Naldi and Vincent Neiger,
Gröbner bases of syzygy modules and multivariate Padé approximation,
slides part 1 and
part 2.
Abstract:
Given elements f_1,…,f_m in a quotient module R^n / N of finite dimension as a K-vector space, where R = K[x_1…x_r] and N is an R-submodule of R^n, we consider the problem of computing a Gröbner basis of the module of syzygies of (f_1,…,f_m). This is the set of vectors (p_1,…,p_m) in R^m such that p_1f_1+…+p_mf_m = 0. An iterative algorithm for this problem was given by Marinari, Möller, and Mora (1993) using a dual representation of quotient as the kernel of a collection of linear functionals.
We will present two recent complexity improvements upon this approach. One
incorporates fast linear algebra operations, by leveraging the
multiplication matrices of the variables in the quotient module. The
other one introduces a divide-and-conquer scheme which generalizes to
several variables Beckermann-Labahn's recursive approach for matrix
Padé and rational interpolation problems. To highlight the interest of
the latter method, we show a complexity improvement in the specific
case of bivariate Padé approximation.
November 25th:
Federico Olimpieri,
Categorifying Intersection Types,
slides.
Abstract:
We study a family of distributors-induced bicategorical models of
lambda-calculus, proving that they can be syntactically presented via
intersection type systems. We first introduce a class of 2-monads
whose algebras are monoidal categories modelling resource
management. We lift these monads to distributors and define a
parametric Kleisli bicategory, giving a sufficient condition for its
cartesian closure. In this framework we define a proof-relevant
semantics: the interpretation of a term associates to it the set of
its typing derivations in appropriate systems. We prove that our model
characterize solvability, adapting reducibility techniques to our
setting. We conclude by describing wo examples of our construction.
October 28th:
Benjamin Dupont,
A formal description of coherence in abstract rewriting,
slides.
Abstract:
In higher-dimensional representation theory, categorification is a
tool consisting in replacing representations of an algebra by vector
spaces and linear maps by higher-dimensional categories and linear
functors to obtain an enriched structure. Given an algebra A, a
natural setting to categorify A is to define a 2-category presented by
diagrammatic generators and relations in terms of string diagrams, and
to prove the isomorphism between its Grothendieck group and the
algebra. To that extent, a relevant question is to compute a set of
linear bases for all the sets of 2-cells of the category. In this
talk, we will show how these problems can be tackled using
3-dimensional linear rewriting theory. In particular, we describe the
difficulties occuring in the proofs of termination and confluence in
that context. We will illustrate these methods for the family of
Khovanov-Lauda-Rouquier algebras arising in the process of
categorifying a quantum group. We will discuss the construction of the
categorification in that case, and how usual rewriting methods can be
extend to compute bases for this latter.
October 14th:
Cameron Calk,
A formal description of coherence in abstract rewriting,
slides.
Abstract:
Kleene algebras have their origins in the theory of regular languages,
but have more recently been used to describe properties of abstract
rewriting systems (ARS). The latter capture equivalences between
elements of a set via directed transformations. On the other hand,
polygraphic rewriting techniques provide information about
equivalences between higher dimensional objects such as paths. In
particular, the question of coherence arises: are any two undirected
paths equivalent modulo higher dimensional cells? In this talk we will
see how the formal description of ARS via Kleene algebras may be
combined with a higher dimensional approach. After explaining how
properties of ARS may be expressed in Kleene algebras, we will
introduce a notion of 2-Kleene algebra and describe how coherence
properties may be captured therein. Finally, we will discuss the main
result of this work: a formal coherence theorem for ARS. These are the
fruits of a joint work with Eric Goubault, Philippe Malbos and Georg
Struth.
Spring 2021
July 1st:
Bérénice Delcroix-Oger,
Operads with compatible CL-shellable partition posets admit a PBW basis,
slides.
Abstract:
In 2007, Bruno Vallette built a bridge between posets and operads,
linking a topological property for partition posets (Cohen-Macaulay)
with an algebraic property for operads (being Koszul). While there are
mainly one property refining being Koszul (admitting a PBW basis),
there are several topological properties on posets refining
Cohen-Macaulayness. In a joint work with Joan Bellier-Millès and Eric
Hoffeck, we studied the link between admitting a PBW-basis and
topological properties on posets. After recalling the needed notions
on posets and operads, I will present our results.
June 24th:
Samuele Giraudo,
Clone realizations of semigroup varieties,
slides.
Abstract:
Given a variety V of algebras (presented by generating operations and relations between
some of their compositions), a natural question consists in building a clone realization of
V. This consists in encoding the operations of V by combinatorial objects in such a way
that two equivalent ones have the same representation, and in providing an algorithm to
compute the representation of the functional composition of several operations. We introduce
the clone of colored words, which is a clone containing several substructures providing
clone realizations of some varieties. We obtain in this way clone realizations of various
classes of semigroups (commutative, left/right-regular bands, semilattices, etc.).
June 17th:
Cyrille Chenavier,
Presenting isomorphic finitely presented modules
by equivalent matrices: a constructive approach,
slides.
Abstract:
A multidimensional linear system can be studied by means of its
associated module, presented by the unknown functions of this system
subject to the equations. Testing whether two linear systems/modules are
isomorphic (the so-called equivalence problem) is an important issue. In
this presentation, I will first recall from a previous work of
Thomas Cluzeau and Alban Quadrat an explicit characterisation for a
module morphism to be an isomorphism. Then, I will recall how they
obtained a constructive version of a result due to Fitting, which shows
how to enlarge matrices presenting isomorphic modules by blocks of zeros
and identities to get equivalent matrices. Finally, I will present an
inductive procedure for reducing the size of these two equivalent
matrices. It turns out that this procedure enables us to recover a result
due to Warfield.
May 27th:
Simon Forest,
Rewriting for Gray categories,
slides.
Abstract:
Recent works have extended the use of classical rewriting to higher
dimensions. Among them, several (Lafont, Guiraud, Malbos, ...) have
used strict categories as a framework for studying presentations of
higher structures. Even though the simplicity of strict categories
made them a prime candidate for such generalization, their use for
this task is problematic in several aspects. In particular, since
strict categories are not equivalent to weak categories starting from
dimension 3, they can not be used to give the most general definition
of weak structures. In this presentation, I will show how to extend
the rewriting toolkit to 3-dimensional weak categories, which are
known to be equivalent to Gray categories.
May 13th:
Pedro Tamaroff,
Diamond lemma through homotopical algebra,
slides.
Abstract:
The Diamond Lemma is a result indispensable to those studying
associative (and other types of) algebras defined by generators and
relations. In this talk, I will explain how to approach this
celebrated result through the lens of homotopical algebra: we will see
how every multigraded resolution of a monomial algebra leads to "its
own" Diamond Lemma, which is hard-coded into the Maurer-Cartan
equation of its tangent complex. For the reader familiar with
homotopical algebra, we hope to provide a conceptual explanation of a
very useful but perhaps technical result that guarantees uniqueness of
normal forms through the analysis of "overlapping ambiguities". For a
reader familiar with Gröbner bases or term rewriting theory, we hope
to offer some intuition behind the Diamond Lemma and at the same time
a framework to generalize it to other algebraic structures and
optimise it. This is joint work with Vladimir Dotsenko
(arXiv:2010.14792).
April 29th:
Amar Hadzihasanovic,
Diagrammatic sets and homotopically sound
rewriting,
slides.
Abstract:
I will give an introduction to the theory of diagrammatic sets, a
combinatorial framework for higher-dimensional rewriting, designed to
be as close as possible to polygraphs in practice, but remain provably
“sound for homotopical algebra”, thanks to a tighter connection to
combinatorial models of homotopy types. I will sketch how diagrammatic
sets support a model of weak higher categories, specialising to a
model of higher groupoids that satisfies a version of the homotopy
hypothesis. If there is time, I will discuss the “smash product of
pointed diagrammatic sets” and its application to universal algebra,
which initially motivated the whole project.
April 22nd:
Clemens Hofstadler,
Computing noncommutative Gröbner bases and
certifying operator identities,
slides.
Abstract:
We will recall the main results of the theory of Gröbner bases in the free
algebra. Additionally, we discuss an adaption of Faugère’s F4 algorithm to
this setting, which allows us to compute noncommutative Gröbner bases
using linear algebra. As an application of noncommutative Gröbner bases,
we also present a recently developed framework to rigorously prove operator
identities by verifying ideal membership of noncommutative polynomials.
April 15th:
Maxime Bros,
Gröbner Bases in Cryptography through the example
of the Rank Decoding Problem,
slides.
Abstract:
In this talk, I will briefly explain the purpose of asymmetric
cryptography and why one is looking for hard problems in order to
design secure cryptographic schemes. Then, I will introduce the
celebrated post-quantum cryptography which is a response to the threat
of quantum computers. Gröbner Basis can be used in cryptanalysis (the
"attack" part of cryptography) and I will present our attack against
one of the main problem in post-quantum cryptography, namely the Rank
Decoding Problem.
April 1st:
Léonard Guetta,
Polygraphic homology of strict
omega-categories,
slides.
Abstract:
In this talk, I will present the main results of my PhD thesis, which
revolved around the polygraphic homology of strict
omega-categories. After recalling the definition of polygraphic
homology of strict omega-categories and its link to rewriting theory,
I will explain how it compares but generally differs from another
homology for strict omega-categories, which is the one defined via the
Street nerve functor (which I will recall too). I will then try to
give abstract and concrete criteria to detect the strict
omega-categories for which both homologies do coincide, and I will use
these criteria to give many examples of such strict
omega-categories. I will end the talk by introducing the notion of
"bubble-free 2-polygraph" and states the "bubble-free conjecture",
which roughly says that these 2-polygraphs have good homological and
homotopical properties.
March 18th:
Isaac Ren,
Operadic rewriting and Koszulness,
slides.
Abstract:
Shuffle operads were introduced to make explicit the symmetric
actions on symmetric operads. Rewriting methods were then applied
to symmetric operads via these shuffle operads: in particular, a
notion of Gröbner basis was introduced by Dotsenko and Khoroshkin
for shuffle operads using a given monomial order. First, we recall
the definitions of Gröbner bases and Koszulness for shuffle
operads. Then, we fit this rewriting approach in the more general
framework of higher dimensional rewriting for shuffle
operads. This framework allows us to explicitly construct an
operadic resolution à la Anick, and we show a sufficient condition
for Koszulness for operads.
March 4th and 11th:
Benjamin Dupont,
Linear polygraphs,
slides.
February, 25th and March 4th:
Cyrille Chenavier,
Introduction to linear rewriting: Gröbner bases
and reduction operators,
slides.
February, 18th:
Cameron Calk,
Strategies and resolutions,
slides.
February, 11th:
Maxime Lucas,
Homotopical motivations of higher-dimensional
rewriting,
slides.
January, 28th:
Uran Meha,
3-polygraphs and Squier's completion Theorem,
slides.
January, 21st:
Nohra Hage,
2-polygraphs and string rewriting,
slides.
January, 14th:
Cameron Calk
and Benjamin Dupont,
Abstract rewriting and String rewriting
systems, slides
part 1 and
part 2.
