Showing cs.LOShow all
3 papers · 1 filter
cs.LO2026
How (and when) can you fit examples to logic-based hypothesis classes over infinite structures?
Michael Benedikt, Alessio Mansutti
We study fitting problems, sometimes called ``training problems'', where we have a finite sample consisting of inputs and outputs, and we want to know whether there is a function i…
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.LO2025
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…