TL;DR
This paper refines the concept of "polite theories," a crucial extension to the Nelson-Oppen framework for combining decision procedures. By fixing a subtle flaw in the original definition of politeness and introducing new combination theorems, the authors enable the modular combination of a wider range of theories, including those with finite domains, which are common in areas like bit-vector reasoning.
What Problem Does This Paper Address?
Combining decision procedures for different theories is a cornerstone of automated reasoning, particularly in formal verification. The classic Nelson-Oppen framework is powerful but has a significant limitation: it requires theories to be "stably-infinite." This means that for any satisfiable formula, there must exist an interpretation with infinite domains for certain sorts. Unfortunately, many practical theories, such as the theory of bit-vectors (essential for hardware and software verification), are not stably-infinite because they inherently deal with finite domains. This limitation prevents the direct application of Nelson-Oppen to these important theories.
Previous work introduced "polite theories" as a way to overcome this restriction, allowing combinations with arbitrary theories. However, the original definition of politeness had a subtle flaw that could lead to incorrect results. This paper addresses this by:
- Correcting the definition of politeness: Specifically, a modification to the "finite witnessability" property is introduced to fix a correctness issue.
- Extending combination theorems: The authors provide new theorems that describe how politeness is preserved when combining polite theories and when instantiating theories (e.g., by identifying sorts). This leads to a more general framework for combining multiple polite theories.
Methods
The paper builds upon the concept of "polite theories," which are theories that are both "smooth" and "finitely witnessable" with respect to a set of sorts.
- Smoothness: This property ensures that if a theory has an interpretation satisfying a formula, it also has interpretations with arbitrarily large domains for specified sorts. This allows for "resizing structures upwards."
- Finite Witnessability: This property, which has been refined in this paper, allows for the construction of a "minimal" structure for a theory. The corrected definition involves a witness function that, given a formula, produces a new formula that is equivalent and can be satisfied by a structure whose relevant domains are "small" enough. The key correction involves incorporating an "arrangement" of shared variables into the witness condition, which was missing in the original definition and led to counterexamples.
The paper then presents new combination theorems:
- Combination of Two Polite Theories: A theorem shows that combining two polite theories preserves politeness with respect to a specific set of sorts, laying the groundwork for iterative combinations.
- Theory Instantiation: A theorem demonstrates that merging two sorts in a theory (by identifying them with a single new sort) preserves politeness. This is crucial for adapting theories to specific needs, like unifying index and element sorts in array theories.
- Combination of Multiple Polite Theories: A general theorem is provided for sequentially combining multiple polite theories, extending the framework to more complex scenarios.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- The subtle flaw in "finite witnessability" was critical: The paper highlights how a seemingly minor omission (the arrangement of shared variables) in the original definition of finite witnessability could lead to the incorrect conclusion that certain combinations were satisfiable when they were not. This underscores the importance of precise definitions in formal methods.
- Politeness is a powerful abstraction: The concept of politeness provides a robust way to combine theories that are not necessarily stably-infinite, opening up the Nelson-Oppen framework to a much wider range of practical theories, including those with finite domains.
- Theory instantiation preserves politeness: The finding that merging sorts in a theory doesn't destroy its politeness is significant. It means that we can tailor theories (e.g., by making indices and elements the same sort) and still benefit from the polite combination framework.
- Iterative combination is key: The paper's contribution to combining multiple polite theories sequentially is essential for building complex verification systems that rely on the integration of many specialized decision procedures.
Key Results
- A corrected definition of finite witnessability is provided, which fixes a correctness issue in the original definition and is crucial for the validity of the combination theorems.
- A theorem is presented showing that the combination of two polite theories preserves politeness with respect to a derived set of sorts.
- A theorem demonstrates that theory instantiation (merging sorts) preserves politeness.
- A general theorem for combining multiple polite theories sequentially is established, enabling the construction of decision procedures for complex combinations of theories.
- The paper provides examples illustrating the application of these theorems, such as combining array theories and adapting them for bit-vector domains.
Limitations and Future Work
- Proof Omissions: Due to space limitations, the proofs for the theorems are omitted in the paper and are available in a separate technical report.
- Politeness of Specific Theories: While the paper asserts that the proofs of politeness for theories of equality, arrays, sets, and multi-sets are likely still correct with the new definition, it notes that proofs for the theory of lists and the politeness of "shiny theories" might have issues in their current form and require further investigation.
- Efficient Witness Functions: The authors express interest in finding more efficient witness functions that minimize the number of variables involved in the arrangement shared by all theories.
- Politeness of Other Theories: Future work includes investigating the politeness of other common theories, such as inductive data-types, and exploring general theories of inductive data-types.
Summary updated