Quivers and their representations offer a natural language for formulating and solving various matrix problems. In this talk, we will start with an elementary approach to the subject and proceed through the lens of the representation theory of associative algebras. We then present Gabriel’s celebrated theorem, which classifies quivers with only finitely many indecomposable representations. Finally, we discuss how the theory developed by Auslander and Reiten provides a method for constructing (many of) the indecomposable representations. The talk will be accessible and requires only a background in linear algebra.

The parity index problem of tree automata asks, given a regular tree language L and a set of priorities J, is L J-feasible, that is, recognized by a nondeterministic parity automaton with priorities J. The minimal such J for a language is called its Mostowski index. This is a long-standing open problem, of which only a few sub-cases and variations are known to be decidable. Starting from the work from Colcombet and Löding on this same problem, we provide a new characterization of the J-feasibility, using tools from the parity game literature. We add some counters to Lehtinen’s register game, originally used to solve parity games in quasipolynomial time, and use this novel game to characterize J-feasibility. This provides a simple alternative proof to Colcombet and Löding’s reduction. Starting from this reduction, we exhibit two other characterizations, linking the index problem with universal trees and with a parameterized version of the Strahler number, a measure of the branching degree of a finite-depth tree. While we do not solve the decidability of the index problem, our work makes the state-of-the-art more accessible and brings to light the deep relationships between the J-feasability of a language and attractor decompositions, universal trees and Lehtinen’s register game.

In distributed computing, graphs model independent computational units that can communicate only with their neighbors. In this setting, the quality of an algorithm is informally measured either by the amount of exchanged messages, or by the distance the information has to travel during the execution. In this context, simple problems in the centralized setting (such as testing acyclicity or 2-colorability) become hard. However, they become easier if an oracle (knowing the full graph) is allowed to give additional information. For example, a way for the oracle to certify k-colorability consists in giving its color to each node (which may then check that the coloring is proper and uses at most k colors).

The goal of local certification is to minimize the amount of global information needed, while making sure the nodes can collectively test some property even when the oracle is not trustworthy. The sketch above shows that coloration lies among the easiest non-trivial properties to locally certify.

This talk is about presenting the notion of local certification based on joint works with Nicolas Bousquet, Linda Cook, Laurent Feuilloley, and Sébastien Zeitoun. We provide examples of graph properties to illustrate what is easy/hard to certify. We discuss meta-theorems for local certification as well as open problems.

Many different kinds of formal systems may be presented as projection functors p : D → C from a more or less complicated category D to some simpler category C, so that natural logical and computational questions about these systems are reduced to lifting problems along the functor. In the talk I will discuss joint work with Paul-André Melliès applying this perspective to automata and formal languages, which leads naturally to a generalization of the theory of regular and context-free languages to languages of arrows in arbitrary categories. Most of the talk will focus on finite-state automata, but time permitting I will also discuss regular and context-free grammars.

Main references by PAM and NZ:

* Functors are type refinement systems, POPL 2015, https://doi.org/10.1145/2676726.2676970 * The categorical contours of the Chomsky-Schützenberger representation theorem, LMCS 21:2, https://doi.org/10.46298/lmcs-21(2:12)2025