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.

The notion of a local state classifier was introduced in the context of Lawvere’s first open problem in topos theory. Although this problem itself has already been resolved, the idea of local state classifiers—defined as colimits of all monomorphisms—has potential applications in more general categorical frameworks beyond topos theory.

In this talk, I will not delve into the technical details of topos theory. Instead, I will focus on explaining the definition and core idea of the local state classifier through simple examples. At the end of the presentation, I will briefly introduce my research on a topos-theoretic approach to automata theory, which is based on the fact that the local state classifier of the category of word actions PSh(Σ*) is given by word congruences.

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