Abstract
This paper presents a novel algorithm for the enumeration of all models of a two-variable first-order logic ($FO^2$) sentence over a finite domain. By leveraging a two-phase approach that separates unary and binary substructures, the authors achieve a quadratic delay complexity of $O(n^2)$. This result is nearly optimal, as the space required to represent binary relations in a model is itself $\Omega(n^2)$. The algorithm utilizes a constant-time configuration decision oracle and generalized properties of $FO^2$ to ensure efficient backtracking, significantly outperforming traditional All-SAT approaches.
Introduction
In the fields of logic and database theory, model enumeration is the fundamental task of listing every possible "world" or model that satisfies a given set of logical rules, represented as a sentence $\Gamma$. While significant progress has been made in model counting (determining the number of satisfying assignments) and model sampling (generating a random satisfying assignment), efficient enumeration remains a significant challenge.
Central to this challenge is delay complexity: the maximum time elapsed between the output of any two consecutive models. For many fragments of first-order logic, this delay is often exponential, making the exhaustive listing of models impractical for large domains. This paper focuses on Two-Variable Logic ($FO^2$), a fragment that balances expressivity—sufficient for many description logics—with decidability. The authors demonstrate that for $FO^2$, it is possible to achieve a delay that scales quadratically with the domain size $n$, providing a near-optimal solution for model listing.
The Enumeration Challenge in $FO^2$
Previous techniques for $FO^2$, particularly those adapted from sampling algorithms, often resulted in delays that scaled exponentially with the number of predicates in the sentence. To improve upon this, the authors address the bottleneck of checking whether a partial model can be completed into a full model. In a standard backtracking search, this check (the "decision problem") can be computationally expensive.
The significance of achieving $O(n^2)$ delay cannot be overstated. Because a model containing binary predicates over $n$ elements requires $\Omega(n^2)$ bits to represent, any enumeration algorithm must spend at least that much time simply writing the model to the output. Thus, $O(n^2)$ represents the theoretical lower bound for delay in this context.
Methodology: A Two-Phase Approach
The proposed algorithm decomposes the enumeration task into two distinct phases:
1. Unary Substructure Enumeration
The algorithm first determines a configuration, which defines how many elements in the domain belong to each "1-type" (a complete description of an element's unary properties). The authors prove that determining if a configuration is satisfiable can be done in constant time ($O(1)$). This is achieved by identifying "template configurations"—bounded versions of the problem that represent all possible valid configurations for any domain size.
2. Binary Substructure Enumeration
Once the unary properties (the configuration) are fixed, the algorithm recursively fills in the "2-types" (the relationships between pairs of elements). This phase uses a refined domain recursion strategy.
Key Innovations
- Substructure Decision Oracle: Instead of performing expensive model counting at every step of the search tree, the algorithm uses a backtracking search guided by an oracle that checks the satisfiability of partial substructures.
- Reduction to Configuration Decision: The authors demonstrate that the complex problem of completing a partial model can be reduced to a simpler "configuration decision problem," which is solved in $O(1)$ time using the aforementioned templates.
- Incremental Updates: To maintain the quadratic delay bound, the algorithm updates its internal state incrementally as it explores the search tree, avoiding the overhead of recomputing the state from scratch at each node.
Theoretical Insights
The breakthrough relies on generalizing two classic properties of $FO^2$ to the level of configurations:
- Monotonicity of Satisfiability: If a model exists for a domain of size $n$, a model also exists for size $n+1$.
- Exponential Size Model (ESM) Property: If a sentence is satisfiable, it has a model of size at most exponential in the number of predicates.
By applying these to configurations, the authors show that small "template" configurations can serve as proxies for satisfiability checks across any domain size. Furthermore, the authors demonstrate that these results hold even when the logic includes the equality predicate ($=$), a feature that often complicates the complexity of logical fragments.
Experimental Results
The algorithm was evaluated using benchmark $FO^2$ sentences, such as those describing undirected graphs without isolated vertices. When compared against the standard "All-SAT" approach—which finds a model and then adds a "blocking clause" to find the next—the proposed algorithm showed consistently low and stable delay. The results confirm that $FO^2$ model enumeration is Fixed-Parameter Tractable (FPT) when the size of the logic sentence is treated as the parameter.
Conclusion and Future Work
While the algorithm achieves near-optimal delay relative to the domain size $n$, the constant factor remains sensitive to the number of predicates in the sentence $\Gamma$. For highly complex sentences, this factor can be large.
Future research aims to extend these techniques to more expressive fragments, such as $C^2$ (two-variable logic with counting quantifiers). However, the configuration decision problem for $C^2$ is significantly more complex, and achieving similar polynomial delay bounds remains an open and challenging problem in the field.
Summary updated