标题： 具有二次延迟复杂度的二变量逻辑模型枚举 显示英文标题

标题： Model Enumeration of Two-Variable Logic with Quadratic Delay Complexity

摘要： 我们研究了二阶逻辑函数自由、有限域片段中两个变量的模型枚举问题（$FO^2$）。 具体来说，给定一个$FO^2$句子$\Gamma$和一个正整数$n$，如何枚举$\Gamma$在大小为$n$的域上的所有模型？ 在本文中，我们设计了一种新颖的算法来解决这个问题。 当句子固定时，我们的算法在给定域大小$n$上的延迟复杂度（即产生两个连续模型之间所需的时间）是二次的（至多对数因子）。 这一复杂度几乎是最优的，因为在任何模型中对二元谓词的解释至少需要$\Omega(n^2)$位来表示。 显示英文摘要

摘要： We study the model enumeration problem of the function-free, finite domain fragment of first-order logic with two variables ($FO^2$). Specifically, given an $FO^2$ sentence $\Gamma$ and a positive integer $n$, how can one enumerate all the models of $\Gamma$ 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 $\Omega(n^2)$ bits to represent.