Seminar
Logic Seminar
The Logic seminar is held on Wednesdays, usually at 12-14. If not separately specified, the talks always start at a quarter past.
We occasionally have online talks - the permanent Zoom room for the seminar is: https://helsinki.zoom.us/j/62891400777?pwd=UldCeThTaTJVQjUzUFo4S2ErcndNQT09 (Meeting ID: 628 9140 0777, Passcode: 164195)
The seminar is led by prof. Juha Kontinen and Åsa Hirvonen.
Schedule of the fall term 2026
Extra seminar: Wed 12.8.2026 12-14, C124
Ulla Karhumäki: Permutation groups definable in tame theories
Abstract: I will give an overview about results on (definably) primitive permutation groups in model theory. In particular, I will present the classification of pseudo-finite primitive permutation groups of finite SU-rank. If time permits I will also discuss a related result on generically (n+2)-transitive permutation groups definable in a model of ACF. This is joint work with Nicholas Ramsey.
Wed 2.9.2026 12-14, C124
Anssi Yli-Jyrä: Graph-encoding languages as a special case of 2-stack visibly pushdown languages
Abstract: Visibly pushdown languages (VPL) are known for their attractive closure and decidability properties, unlike their multi-stack generalization, which has already undecidable emptiness. This presentation views an existing sequential encoding (Yli-Jyrä 2019, FSMNLP) for ordered graphs as a two-stack visibly pushdown language (2MVPL). The emergent special structure of graph-encoding languages motivates a decomposition of the pertinent computations and a new model, recurrent incidence automaton, and their languages (RIL). The closure and decision properties of this model and its three restrictions (DRIL, UARIL, GRIL) are studied in relation to VPLs and 2MVPLs.
Extra seminar: Tue 8.9.2026 14-16, C323 (Note the unusual day, time, and place)
Timon Barlag: Recurrent Graph Neural Networks and Arithmetic Circuits
Abstract: We characterise the computational power of recurrent graph neural networks (GNNs) in terms of arithmetic circuits over the real numbers. Our networks are not restricted to aggregate-combine GNNs or other particular types. Generalising similar notions from the literature, we introduce the model of recurrent arithmetic circuits, which can be seen as arithmetic analogues of sequential or logical circuits. These circuits utilise so-called memory gates which are used to store data between iterations of the recurrent circuit. While (recurrent) GNNs work on labelled graphs, we construct arithmetic circuits that obtain encoded labelled graphs as real valued tuples and then compute the same function. For the other direction we construct recurrent GNNs which are able to simulate the computations of recurrent circuits. These GNNs are given the circuit-input as initial feature vectors and then, after the GNN-computation, have the circuit-output among the feature vectors of its nodes.
Our results both deepen our understanding of the capabilities of trained neural networks and open new approaches to study recurrent neural networks using the lens of circuit complexity theory.
Wed 9.9.2026 12-14, C124
Tianwei Zhang: Searching for smallest universal graphs with SAT
Abstract: This work is a case study of how SAT solvers can be used to tackle problems in discrete mathematics. We study induced k-universal graphs: graphs containing every graph on k vertices as an induced subgraph. The central problem is to determine the smallest possible order f(k) of such a graph.
We formulate universality as a propositional synthesis problem in which the target graph itself is represented by Boolean variables. To overcome the resulting large search space, we combine several techniques: dynamic symmetry breaking using the SAT Modulo Symmetries framework, additional symmetry breaking among embeddings of pattern graphs, and a template-based decomposition of the search into independent SAT instances.
Using this framework, we determine f(7)=18 and enumerate the optimal induced k-universal graphs for k <= 6, including the previously unknown value F(6)=264662. We also discuss proof certificates that make these computer-assisted results independently checkable.
Wed 16.9.2026 12-14, C124
no seminar
Wed 23.9.2026 12-14, C124
Juha Kontinen: Aspects of Coherence in Dependence Logic
Abstract: Dependence logic extends first-order logic with dependence atoms, which express that the value of a variable is functionally determined by other variables. Team semantics gives dependence logic a second-order flavour, and even quantifier-free dependence logic formulas can have an NP-complete model-checking problem. This motivates the study of syntactic conditions under which model checking becomes tractable.
The talk starts with a brief introduction to team semantics and dependence logic, and then focuses on coherence, a notion introduced by Jarmo Kontinen to capture when the satisfaction of a formula can be determined by satisfaction by its small subteams. We show that, for quantifier-free formulas, coherence is precisely equivalent to first-order rewritability. We also study the complexity of deciding coherence, obtaining strong undecidability results for dependence logic and a precise complexity classification for propositional dependence logic.
The talk is based on joint work with Timon Barlag, Nicolas Fröhlich, Miika Hannula, Phokion G. Kolaitis, Arne Meier, and Jouko Väänänen: https://arxiv.org/abs/2605.31269
Wed 30.9.2026 12-14, C124
Minna Hirvonen: TBA
Wed 7.10.2026 12-14, C124
Juan Pablo Quijano: Logic over Quantales: Generalized Kripke Structures and Contextual Sound Classification
Abstract: This talk develops an algebraic and logic perspective motivated by the problem of contextual sound classification, in which measurements are organized into a topological and algebraic structure and different listener contexts give rise to different spaces of propositions and interpretations of sound. The sound-classification problem serves here primarily as a motivation for the underlying mathematics: it leads naturally to questions about internal logic, modal structure, and the algebraic semantics of contextual interpretation. In particular, can such contextual interpretations be understood through a generalized form of Kripke semantics?
Following the approach of Marcelino and Resende, I will introduce generalized Kripke models based on pointed stably supported quantales, in which the accessibility relation of a classical Kripke frame is replaced by a distinguished element of a quantale. Ordinary Kripke structures are recovered as the special case given by the quantale of binary relations. I will describe the resulting modal operators and the algebraic characterization of the systems K, T, K4, S4, and S5, together with the corresponding completeness results. Extensions to propositional dynamic logic PDL, computational tree logic CTL, and intuitionistic modal logic illustrate the flexibility of this algebraic approach to modal semantics.
I will then explain how this perspective can be extended beyond relational Kripke semantics. Replacing the quantale of binary relations \mathcal{P}(W\times W) by more general quantales arising from groupoids leads to models given by homomorphisms Q\to\mathcal{O}(G), rather than Q\to\mathcal{P}(W\times W), where Q is a Lindenbaum quantale. This provides a natural connection between quantales, groupoids, and modal logic, and suggests possible semantic frameworks for applications involving hybrid systems and logics of real time and space. The talk concludes by returning to measurement spaces and contextual sound classification, asking how these generalized algebraic and logical structures may provide a broader language for contextual interpretation and computation, and how this perspective connects with questions concerning logic and computation over algebraic structures, including semiring-based approaches.
Wed 14.10.2026 12-14, C124
Wed 21.10.2026 12-14, C124
Exam week, no seminar
Wed 28.10.2026 12-14, C124
Wed 4.11.2026 12-14, C124
Miguel Moreno: TBA
Wed 11.11.2026 12-14, C124
Jean-Charles Belouard: TBA
Wed 18.11.2026 12-14, C124
Wed 25.11.2026 12-14, C124
Corey Switzer: TBA
Wed 2.12.2026 12-14, C124
Wed 9.12.2026 12-14, C124
Wed 16.12.2026 12-14, C124
Exam week, no seminar