Model Enumeration of Two-Variable Logic with Quadratic Delay Complexity

Qiaolan Meng, Juhua Pu, Hongting Niu, Yuyi Wang, Yuanhong Wang, Ondrej Kuzelka

Abstract

We study the model enumeration problem of the function-free, finite domain fragment of first-order logic with two variables (FO2). Specifically, given an FO2 sentence Γ and a positive integer n, how can one enumerate all the models of Γ 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 Ω(n2) bits to represent.
BibTeX
@inproceedings{meng2025model,
  author = {Qiaolan Meng and Juhua Pu and Hongting Niu and Yuyi Wang and Yuanhong Wang and Ondrej Kuzelka},
  title = {{Model Enumeration of Two-Variable Logic with Quadratic Delay Complexity}},
  booktitle = {LICS},
  year = {2025},
  doi = {10.1109/lics65433.2025.00030},
}
Figure