Weihrauch reducibility is a notion from type-2 computability that allows to compare the computational strength of problems, modelled as relations over Baire space. Much like in Reverse Mathematics, any Π¹₂ statement translates naturally to a Weihrauch problem. Unlike Reverse Mathematics, the notion of reducibility is resource sensitive, i.e., a reduction from P to Q is allowed to use Q exactly once. The Weihrauch lattice also comes with a rich algebra of operators that allows for instance to talk about sequential or parallel composition of problems.
This rich structure is in fact not specific to Weihrauch complexity as problems and reductions (almost) correspond to a category of polynomial functors, which share many of the useful operators in Weihrauch complexity.

After introducing these notions, I will discuss two of my works on the structural aspects of the theory where automata played a not-so-expected role.

The first one is about the existence of fixpoints of well-behaved operators for polynomial functors and the encoding of some Weihrauch problems of interest via a fixpoint syntax or, slightly more generally, tree automata. Here a question we left open is decidability of reduction between two syntactically presented problems.

The second concerns the equational theory of certain sets of operators, specifically those that are reminiscent of Kleene lattices. In that setting validity of an inequation correspond exactly to the existence of a kind of simulation between alternating automata, where Duplicator is allowed to simulate several runs at once. I will give a complete axiomatization. Extending the set of operators would probably entail extending the analysis to concurrent automata and automata with runs of countable length.

Links:
The first work, with Ian Price: https://arxiv.org/abs/2601.15420
The second work: https://arxiv.org/abs/2408.14999