Sitemap
A list of all the posts and pages found on the site. For you robots out there, there is an XML version available for digesting as well.
Pages
Posts
publications
Completing the Picture: Complexity of the Ackermann Fragment
Published in European Summer School in Logic, Language and Information, 2022
We show that the satisfiability problem of the Ackermann fragment with equality, when the number of trailing existential quantifiers is bounded, is \({\rm ExpTime}\)-complete.
Daumantas Kojelis
Download Paper
On the Limits of Decision: the Adjacent Fragment of First-Order Logic
Published in 50th International Colloquium on Automata, Languages, and Programming, 2023
We define the adjacent fragment of first-order logic (without equality) and establish decidability of satisfiability.
Bartosz Bednarczyk, Daumantas Kojelis, Ian Pratt-Hartmann
Download Paper
On Homogeneous Models of Fluted Languages
Published in 33rd EACSL Annual Conference on Computer Science Logic, 2025
We show that satisfiable fluted sentences admit special kinds of “nice” models which we call globally/locally homogeneous. We establish that the fluted fragment with periodic counting is decidable for satisfiability, whilst the adjacent fragment with counting is not.
Daumantas Kojelis
Download Paper
The Adjacent Fragment and Quine’s Limits of Decision
Published in Journal of Logic and Computation, 2025
We define the adjacent fragment of first-order logic (with equality) and establish decidability of satisfiability.
Bartosz Bednarczyk, Daumantas Kojelis, Ian Pratt-Hartmann
Download Paper
Understanding the Expressive Power of GNNs with Global Readout
Published in Undergoing Peer Review, 2027
We study the logical expressive power of GNNs with global readout, finding the limit to which C^2 can be used for characterisations
Maurice Funk, Daumantas Kojelis
Download Paper
Constant-Depth Rational-Weight GNNs and their Connection to Schanuel’s Conjecture
Published in Undergoing Peer Review, 2027
We study the relationship between Schanuel’s conjecture and the uniform expressive power of GNNs with sigmoid, tanh, and related activation functions.
Daumantas Kojelis, Carsten Lutz
Download Paper