5 papers
Verifying Quantized GNNs With Readout Is Decidable But Highly Intractable
Artem Chernobrovkin, Marco Sälzer, François Schwarzentruber +1
We introduce a logical language for reasoning about quantized aggregate-combine graph neural networks with global readout (ACR-GNNs). We provide a logical characterization and use…
On Dynamic Programming Theory for Leader-Follower Stochastic Games
Jilles Steeve Dibangoye, Thibaut Le Marre, Ocan Sankur +1
Leader-follower general-sum stochastic games (LF-GSSGs) model sequential decision-making under asymmetric commitment, where a leader commits to a policy and a follower best respond…
Lecture Notes on Verifying Graph Neural Networks
François Schwarzentruber
In these lecture notes, we first recall the connection between graph neural networks, Weisfeiler-Lehman tests and logics such as first-order logic and graded modal logic. We then p…
Linear Planar 3-SAT and Its Applications in Planning
Victorien Desbois, Ocan Sankur, François Schwarzentruber
Several fragments of the satisfiability problem have been studied in the literature. Among these, Linear 3-SAT is a satisfaction problem in which each clause (viewed as a set of li…
A Computationally Grounded Framework for Cognitive Attitudes (extended version)
Tiago de Lima, Emiliano Lorini, Elise Perrotin +1
We introduce a novel language for reasoning about agents' cognitive attitudes of both epistemic and motivational type. We interpret it by means of a computationally grounded semant…