Cover Image

Expressive Power of Graph Transformers via Logic

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Ahvonen, Veeti, Funk, Maurice, Heiman, Damian, Kuusisto, Antti, Lutz, Carsten
Format:	Preprint
Published:	2025
Subjects:	Logic in Computer Science Artificial Intelligence F.4.1; F.1.1; I.2.0
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Logical Characterizations of Recurrent Graph Neural Networks with Reals and Floats
by: Ahvonen, Veeti, et al.
Published: (2024)

Graph neural networks and MSO
by: Ahvonen, Veeti, et al.
Published: (2025)

Cross-Attention and Encoder-Decoder Transformers: A Logical Characterization
by: Ahvonen, Veeti, et al.
Published: (2026)

Graded modal logic and counting message passing automata
by: Ahvonen, Veeti, et al.
Published: (2024)

Neural networks as fuzzy logic formulas
by: Heiman, Damian, et al.
Published: (2026)

Descriptive complexity for neural networks via Boolean networks
by: Ahvonen, Veeti, et al.
Published: (2023)

Probabilistic Shoenfield Machines
by: Bujok, Maksymilian, et al.
Published: (2024)

Fixed-Point Theorems and the Ethics of Radical Transparency: A Logic-First Treatment
by: Alpay, Faruk, et al.
Published: (2025)

On the existence of strong proof complexity generators
by: Krajicek, Jan
Published: (2022)

Extended Nullstellensatz proof systems
by: Krajicek, Jan
Published: (2023)

A Theory for Probabilistic Polynomial-Time Reasoning
by: Chen, Lijie, et al.
Published: (2026)

How to Verify a Turing Machine with Dafny
by: Lederer, Edgar F. A.
Published: (2026)

Structure-Guided Automated Reasoning
by: Bannach, Max, et al.
Published: (2023)

AI-Oracle Machines for Intelligent Computing
by: Wang, Jie
Published: (2024)

OnlineProver: Experience with a Visualisation Tool for Teaching Formal Proofs
by: Perháč, Ján, et al.
Published: (2025)

Hardness of busy beaver value BB(15)
by: Stérin, Tristan, et al.
Published: (2021)

The Luna Bound Propagator for Formal Analysis of Neural Networks
by: LeCates, Henry, et al.
Published: (2026)

Turing machines deciders, part I
by: The bbchallenge Collaboration, et al.
Published: (2025)

Complex Logical Reasoning over Knowledge Graphs using Large Language Models
by: Choudhary, Nurendra, et al.
Published: (2023)

Robust Computation Tree Logic
by: Nayak, Satya Prakash, et al.
Published: (2022)

Modal Logics -- RNmatrices vs. Nmatrices
by: Coniglio, Marcelo E., et al.
Published: (2024)

Hoare meets Heisenberg: A Lightweight Logic for Quantum Programs
by: Sundaram, Aarthi, et al.
Published: (2021)

Globally Interpretable Classifiers via Boolean Formulas with Dynamic Propositions
by: Jaakkola, Reijo, et al.
Published: (2024)

Description Complexity of Unary Structures in First-Order Logic with Links to Entropy
by: Jaakkola, Reijo, et al.
Published: (2024)

From Compactifying Lambda-Letrec Terms to Recognizing Regular-Expression Processes
by: Grabmayer, Clemens
Published: (2024)

On the computational properties of ambivalent sets and functions
by: Normann, Dag, et al.
Published: (2026)

Proof Compression via Subatomic Logic and Guarded Substitutions
by: Barrett, Victoria, et al.
Published: (2025)

Two-Level Type Theory and Applications
by: Annenkov, Danil, et al.
Published: (2017)

How Expressive Are Graph Neural Networks in the Presence of Node Identifiers?
by: Soeteman, Arie, et al.
Published: (2026)

On the Realizability of Prime Conjectures in Heyting Arithmetic
by: Rosko, Milan
Published: (2025)

Probabilistic Epistemic Dynamic Agentive Logic
by: Logan, Shay Allen
Published: (2026)

Locality in Residuated-Lattice Structures
by: Carr, James
Published: (2025)

Degree-preserving Godel logics with an involution: intermediate logics and (ideal) paraconsistency
by: Coniglio, M. E., et al.
Published: (2026)

A Theory of Hanoi Omega-Automata and Games
by: Filiot, Emmanuel, et al.
Published: (2026)

Interpretable classifiers for tabular data via discretization and feature selection
by: Jaakkola, Reijo, et al.
Published: (2024)

Logic of Sets with Atoms
by: Masters, Jake
Published: (2025)

A Real-Analytic Approach to Differential-Algebraic Dynamic Logic
by: Hellwig, Jonathan, et al.
Published: (2025)

Undecidability in Relevant Logic
by: Knudstorp, Søren Brinck
Published: (2026)

Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs
by: de Rezende, Susanna F., et al.
Published: (2019)

Expressivity of bisimulation pseudometrics over analytic state spaces
by: Luckhardt, Daniel, et al.
Published: (2025)