1 citations · 2 across the 4 of their papers we have counts for
4 papers · 1 filter
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…
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…
On two-variable guarded fragment logic with expressive local Presburger constraints
Chia-Hsuan Lu, Tony Tan
We consider the extension of the two-variable guarded fragment logic with local Presburger quantifiers. These are quantifiers that can express properties such as "the number of inc…
Towards a more efficient approach for the satisfiability of two-variable logic
Ting-Wei Lin, Chia-Hsuan Lu, Tony Tan
We revisit the satisfiability problem for two-variable logic, denoted by SAT(FO2), which is known to be NEXP-complete. The upper bound is usually derived from its well known Expone…