Events

Date: 13 July 2026   Time: 13:00 - 14:30     

Location: Room 4.24

We have two post-ICALP speakers who will be visiting us this coming Monday: S P Rishal (Sarva Labs) and Panos Aivasiliotis (Potsdam).

Talk 1: Set automata and limits of decidability of two-variable logic on data words

S P Rishal (Sarva Labs)

Abstract

Joint work with Shibashis Guha and Amaldev Manuel. Motivations from verification and XML for reasoning about values from an infinite domain have given rise to the study of logics and automata over data words. A data word is a finite word in which each position carries a label from a finite alphabet and a data value from an infinite domain that can be tested only for equality. A natural logic to consider over data words is first-order logic with a data-equality predicate that is satisfied by two positions when they carry the same data value. This logic however is too expressive, having an undecidable satisfiability problem, with undecidability persisting even when the logic is restricted to three variables. It is a well-known result that the satisfiability problem of the two-variable fragment of first-order logic on data words is decidable. In this talk, we present a decidable extension of this two-variable logic. We extend the two-variable logic on data words with guarded regular binary predicates of the form L(x,y) that is satisfied by positions x and y if they carry the same data value and the factor strictly between x and y is in the regular language L. Motivated by the algebraic approach to regular languages, we consider the logic with guarded regular predicates recognised by a monoid. We characterise the class of monoids for which the resulting extension of the two-variable logic is decidable. Our proof is automata-theoretic. We present an automaton formalism called set automaton, and identify a subclass called ordered quasi-normal set automata that has a decidable emptiness problem by reduction to the emptiness problem of ordered multicounter automata. The set updates used in the automaton form a semigroup of relations. We show that the two-variable logic extended with guarded regular predicates recognised by a monoid M is expressively equivalent to a quasi-normal set automaton with the monoid of relations M. In particular, if M is idempotent and its two-sided ideals are linearly ordered, then the resulting automaton is ordered and the decidability result follows.

Talk 2: Symmetric Parameterised Holants on Hypergraphs: Towards a Classification for Parameterised VCSPs

Panos Aivasiliotis (Potsdam)

Abstract

Joint work with Andreas Göbel, Marc Roth We study the complexity of the parameterised counting constraint satisfaction problem: given a set of constraints over a set of variables and a positive integer k, how many ways are there to assign k variables to 1 (and the others to 0) such that all constraints are satisfied. Existing work has so far exclusively focused on restricted settings such as finding and counting homomorphisms between relational structures due to Grohe (JACM 2007) and Dalmau and Jonsson (TCS 2004), or the case of finite constraint languages due to Creignou and Vollmer (SAT 2012), and Bulatov and Marx (SICOMP 2014). In this work, we tackle a more general setting of Valued Parameterised Counting Constraint Satisfaction Problems (VCSPs) with infinite constraint languages. In this setting we are able to model significantly more general problems such as (weighted) parameterised factor problems on hypergraphs and counting weight-k solutions of systems of linear equations, not captured by existing complexity classifications. We express parameterised VCSPs as parameterised Holant problems on uniform hypergraphs, and we establish complete and explicit complexity dichotomy theorems. For resolving the P vs. #P question, we mainly rely on hypergraph gadgets, the existence of which we prove using properties of degree sequences necessary for realisability in uniform hypergraphs. For the FPT vs. #W[1] question, we build upon the recently established combinatorial toolkit for parameterised holants on the special case of graphs by Aivasiliotis et al. (ICALP 2025) and also rely on an extension of the framework of the homomorphism basis due to Curticapean, Dell and Marx (STOC 17) to uniform hypergraphs. As a technical highlight, we also employ Curticapean's "CFI Filters'' (SODA 2024) to establish polynomial-time algorithms for isolating vectors in the homomorphism basis.