Motivated by the notion of strong computable type for sets in computable analysis, we define the notion of strong computable type for G-shifts, where G is a finitely generated group with decidable word problem. A G-shift has strong computable type if one can compute its language from the complement of its language.

We obtain a characterization of G-shifts with strong computable type in terms of a notion of minimality with respect to properties with a bounded computational complexity. We provide a self-contained direct proof, and also explain how this characterization can be obtained from an existing similar characterization for sets by Amir and Hoyrup, and discuss its connexions with results by Jeandel on closure spaces. We apply this characterization to several classes of shifts that are minimal with respect to specific properties.

This provides a unifying approach that not only generalizes many existing results but also has the potential to yield new findings effortlessly. In contrast to the case of sets, we prove that strong computable type for G-shifts is preserved under products. We conclude by discussing some generalizations and future directions.

This is a joint work with Benjamin Hellouin de Menibus.

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

The classical Dirichlet theorem on arithmetic progressions states that there are infinitely many primes in a given arithmetic progression with a trivial necessary condition. In this talk, we prove a “reversed” version of this theorem, which may be called Telhcirid's theorem on arithmetic progressions, i.e., we prove that there are infinitely many primes whose reverse of radix representation is in a given arithmetic progression except in some degenerate cases. This is a joint work with Gautami Bhowmik (University of Lille).