5 citations · 8 across the 19 of their papers we have counts for
22 papers
Transformer Heads Looking for Order
Jasper van Doornmalen, Alexander Kozachinskiy, Corinna Mathwieser +4
In this note, we show that the problem of checking, whether a sequence of bits is ordered, is not doable by 1-head 1-layer transformers but is doable by a 2-head 1-layer transforme…
A Unifying Relational Perspective on Expressive Lottery Tickets
Lorenz Kummer, Samir Moustafa, Anatol Ehrlich +4
Graph neural networks (GNNs) are widely used, but how parameter sparsity affects the expressivity of relational (RGNNs) and temporal (TGNNs) variants is poorly understood. The Stro…
Structural Preservation and the Logical Expressiveness of Graph Neural Networks
Przemysław Andrzej Wałęga, Bernardo Cuenca Grau
Bridges between graph neural networks (GNNs) and logical formalisms have been established by fixing architectural choices, such as the types of aggregation, combination, and activa…
Preservation Theorems for Unravelling-Invariant Classes: A Uniform Approach for Modal Logics and Graph Neural Networks
Przemysław Andrzej Wałęga, Bernardo Cuenca Grau
We study preservation theorems for modal logics over finite structures with respect to three fundamental semantic relations: embeddings, injective homomorphisms, and homomorphisms.…
Parity, Sensitivity, and Transformers
Alexander Kozachinskiy, Tomasz Steifer, Przemysław Wałȩga
Understanding what neural architectures can and cannot compute is a central challenge in the theory of AI. One of the fundamental problems in this context is the PARITY task, which…
Description Logics with Two Types of Definite Descriptions: Complexity, Expressiveness, and Automated Deduction
Michał Sochański, Przemysław Andrzej Wałęga, Michał Zawidzki
Definite descriptions are expressions of the form "the unique satisfying property ," which allow reference to objects through their distinguishing characteristics. They play…
Aggregate-Combine-Readout GNNs Are More Expressive Than Logic C2
Stan P Hauke, Przemysław Andrzej Wałęga
In recent years, there has been growing interest in understanding the expressive power of graph neural networks (GNNs) by relating them to logical languages. This research has been…
The Logical Expressiveness of Temporal GNNs via Two-Dimensional Product Logics
Marco Sälzer, Przemysław Andrzej Wałęga, Martin Lange
In recent years, the expressive power of various neural architectures -- including graph neural networks (GNNs), transformers, and recurrent neural networks -- has been characteris…
The Correspondence Between Bounded Graph Neural Networks and Fragments of First-Order Logic
Bernardo Cuenca Grau, Eva Feng, Przemysław Andrzej Wałęga
Graph Neural Networks (GNNs) address two key challenges in applying deep learning to graph-structured data: they handle varying size input graphs and ensure invariance under graph…
Goal-Driven Reasoning in DatalogMTL with Magic Sets
Shaoyu Wang, Kaiyue Zhao, Dongliang Wei +4
DatalogMTL is a powerful rule-based language for temporal reasoning. Due to its high expressive power and flexible modeling capabilities, it is suitable for a wide range of applica…
Hybrid Modal Operators for Definite Descriptions
Przemysław Andrzej Wałęga, Michał Zawidzki
In this paper, we study computational complexity and expressive power of modal operators for definite descriptions, which correspond to statements `the modal world which satisfies…
Expressive Power of Temporal Message Passing
Przemysław Andrzej Wałęga, Michael Rawson
Graph neural networks (GNNs) have recently been adapted to temporal settings, often employing temporal versions of the message-passing mechanism known from GNNs. We divide temporal…
Fuzzy Datalog over Arbitrary t-Norms
Matthias Lanzinger, Stefano Sferrazza, Przemysław A. Wałęga +1
One of the main challenges in the area of Neuro-Symbolic AI is to perform logical reasoning in the presence of both neural and symbolic data. This requires combining heterogeneous…
Practical Reasoning in DatalogMTL
Dingmin Wang, Przemysław A. Wałęga, Pan Hu +1
DatalogMTL is an extension of Datalog with metric temporal operators that has found an increasing number of applications in recent years. Reasoning in DatalogMTL is, however, of hi…
Seminaive Materialisation in DatalogMTL
Dingmin Wang, Przemysław Andrzej Wałęga, Bernardo Cuenca Grau
DatalogMTL is an extension of Datalog with metric temporal operators that has found applications in temporal ontology-based data access and query answering, as well as in stream re…
MeTeoR: Practical Reasoning in Datalog with Metric Temporal Operators
Dingmin Wang, Pan Hu, Przemysław Andrzej Wałęga +1
DatalogMTL is an extension of Datalog with operators from metric temporal logic which has received significant attention in recent years. It is a highly expressive knowledge repres…
Data Complexity and Rewritability of Ontology-Mediated Queries in Metric Temporal Logic under the Event-Based Semantics (Full Version)
Vladislav Ryzhikov, Przemyslaw Andrzej Walega, Michael Zakharyaschev
We investigate the data complexity of answering queries mediated by metric temporal logic ontologies under the event-based semantics assuming that data instances are finite timed w…
Answer Set Programming Modulo `Space-Time'
Carl Schultz, Mehul Bhatt, Jakob Suchan +1
We present ASP Modulo `Space-Time', a declarative representational and computational framework to perform commonsense reasoning about regions with both spatial and temporal compone…
Visual Explanation by High-Level Abduction: On Answer-Set Programming Driven Reasoning about Moving Objects
Jakob Suchan, Mehul Bhatt, Przemysław Wałęga +1
We propose a hybrid architecture for systematically computing robust visual explanation(s) encompassing hypothesis formation, belief revision, and default reasoning with video data…
Non-Monotonic Spatial Reasoning with Answer Set Programming Modulo Theories
Przemysław Andrzej Wałęga, Carl Schultz, Mehul Bhatt
The systematic modelling of dynamic spatial systems is a key requirement in a wide range of application areas such as commonsense cognitive robotics, computer-aided architecture de…
ASPMT(QS): Non-Monotonic Spatial Reasoning with Answer Set Programming Modulo Theories
Przemysław Andrzej Wałęga, Mehul Bhatt, Carl Schultz
The systematic modelling of \emph{dynamic spatial systems} [9] is a key requirement in a wide range of application areas such as comonsense cognitive robotics, computer-aided archi…
Reasoning for Moving Blocks Problem: Formal Representation and Implementation
P. A. Wałȩga
The combined approach of the Qualitative Reasoning and Probabilistic Functions for the knowledge representation is proposed. The method aims at represent uncertain, qualitative kno…