Showing cs.LOShow all
3 papers · 1 filter
cs.LO2025
Analysis of logics with arithmetic
Michael Benedikt, Chia-Hsuan Lu, Tony Tan
We present new results on finite satisfiability of logics with counting and arithmetic. One result is a tight bound on the complexity of satisfiability of logics with so-called loc…
cs.LO2024
Decidability of Graph Neural Networks via Logical Characterizations
Michael Benedikt, Chia-Hsuan Lu, Tony Tan
We present results concerning the expressiveness and decidability of a popular graph learning formalism, graph neural networks (GNNs), exploiting connections with logic. We use a f…
cs.LO2014
On the variable hierarchy of first-order spectra
Eryk Kopczynski, Tony Tan
The spectrum of a first-order logic sentence is the set of natural numbers that are cardinalities of its finite models. In this paper we study the hierarchy of first-order spectra…