2026 Seminars
Click here to go back to the main page
Date: May 05, 2026
Speaker: Jacques Sakarovitch
(IRIF - CNRS/Paris Cité University and LTCI - Télécom Paris, Institut Polytechnique de Paris)
Title: Not all (semi)rings are strong
Abstract:
The talk's title refers to the answer to a question that was left open for 20 years. The talk's purpose is also to introduce the weighted finite automata, a computation model which will be the matter of the second talk.
Finite automata are the simplest computation model, the simplest type of machines that accepts or reject sequences of symbols, at the bottom of any complexity hierarchy of machines, inevitably topped by Turing machines. The fundamental result, due to S. Kleene, states that the set of sequences
accepted by a finite automaton can be described by means of the two binary operations of union and product, and a unary operation, called '(Kleene) star', which is the union of all powers of its operand, and conversely.
Weighted finite automata associate with every sequence of symbols a coefficient, taken in a semiring, instead of deciding between rejection or acceptance, 0 or 1, only. The variety of possible sets of coefficients, from probability to set of words, makes the richness of the model. Finite automata accept set of sequences, called languages, weighted finite automata realise (formal power) series.
Kleene's result naturally generalises to weighted finite automata but raises the problem of the definition of the star operation of a series. In contrast with the case of languages, the star of a series is not always defined, as the star is not always defined in the weight semiring. The identity:
(s_0 + s_p)* = (s_0)* (s_p (s_0)*)*
where s_0 and s_p are respectively the 'constant term' and the 'proper part' of a series s, is central in this theory, both for characterising the series whose star is defined and for proving that rational series are realised by weighted finite automata (one direction of Kleene Theorem).
In my book 'Elements of Automata Theory', I give a proof of the above identity under the hypothesis that the weight semiring has the property that the product of two summable families is a summable
family. I call such semirings 'strong' and even though all semirings that I knew are strong, I stated the conjecture that there should exist some semirings which are not strong.
In this talk, and after setting the framework of the topological approach to the definition of star and recalling the proof of the quoted theorem, I present a construction that provides an example of a semiring --- indeed, a ring --- which is not strong.
Joint work with David Madore (LTCI - Télécom Paris, IPP)
Date: April 28, 2026
Speaker: Eduardo Marcos (IME - USP)
Title: Recobrimento e graduações de K-categorias, a categoria smash e recobrimento de Galois.
Abstract:
Definirei o conceito de k-categoria graduada e ação de grupos em k-categorias, definirei o que é o recobrimento de Galois para ações de grupos e o que é o produto smash para categorias graduadas. (O conceito de k-categorias graduadas por grupos, será também definido) e de skew categoria para categorias com G-ações. Provaremos resultados similares aos de Green, e Cohen-Montgomery, nesse contexto. Se tiver tempo falarei de consequências para a cohomologia de Hochschild.
Os resultados estão em dois trabalhos em coautoria com Claude Cibils.