Model Enumeration of Two-Variable Logic with Quadratic Delay Complexity

Abstract

We study the model enumeration problem of the function-free, finite domain fragment of first-order logic with two variables ($F{O}^2$). Specifically, given an $F{O}^2$ sentence $\hat{I}“$ and a positive integer $n$, how can one enumerate all the models of $\hat{I}“$ over a domain of size $n$? In this paper, we devise a novel algorithm to address this problem. The delay complexity, the time required between producing two consecutive models, of our algorithm is quadratic in the given domain size $n$ (up to logarithmic factors) when the sentence is fixed. This complexity is almost optimal since the interpretation of binary predicates in any model requires at least $\hat{I}\text{c◯}(n^2)$ bits to represent.

16 pages, 4 figures and to be published in Fortieth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)