6 papers
Two Variables and Two-Dimensional Structures
Bartosz Jan Bednarczyk, Daumantas Kojelis, Krzysztof Szymański
We study the two-variable fragment FO^2 of first-order logic over two-dimensional structures. Formulae may employ two linear orders <=_1, <=_2, their successor relations S_1, S_2,…
Constant-Depth Rational-Weight GNNs and their Connection to Schanuel's Conjecture
Daumantas Kojelis, Carsten Lutz
A landmark result states that the expressive power of graph neural networks (GNNs) is bounded from above by the 1-dimensional Weisfeiler-Leman (1-WL) test. We ask whether a constan…
Towards Understanding the Expressive Power of GNNs with Global Readout
Maurice Funk, Daumantas Kojelis
We study the expressive power of message-passing aggregate-combine-readout graph neural networks (ACR-GNNs). Particularly, we focus on the first-order (FO) properties expressible b…
On Homogeneous Model of Fluted Languages
Daumantas Kojelis
We study the fluted fragment of first-order logic which is often viewed as a multi-variable non-guarded extension to various systems of description logics lacking role-inverses. In…
The Adjacent Fragment and Quine's Limits of Decision
Bartosz Bednarczyk, Daumantas Kojelis, Ian Pratt-Hartmann
We introduce the adjacent fragment AF of first-order logic, obtained by restricting the sequences of variables occurring as arguments in atomic formulas. The adjacent fragment gene…
On the Limits of Decision: the Adjacent Fragment of First-Order Logic
Bartosz Bednarczyk, Daumantas Kojelis, Ian Pratt-Hartmann
We define the adjacent fragment AF of first-order logic, obtained by restricting the sequences of variables occurring as arguments in atomic formulas. The adjacent fragment general…