Polite Theory Combination for Automated Reasoning

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 216 papers48 conceptsfrozen 2026-10-04

Satisfiability Modulo Theories (SMT) solvers are the engines behind modern software verification, but their power comes from a difficult balancing act: combining disparate mathematical theories—like integers, arrays, and bit-vectors—into a single, coherent reasoning framework. The standard method for this, the Nelson-Oppen procedure, relies on a property called stable infiniteness, which assumes that if a formula has a model, it can always be satisfied by an infinite one.

However, many practical domains are inherently finite. A 32-bit integer (bit-vector) cannot be "scaled up" to an infinite domain without changing its fundamental properties. To bridge this gap, researchers have developed the framework of polite theory combination, which allows solvers to soundly integrate finite and infinite theories.

The Bottleneck of Smoothness

For a theory to be "polite," it must satisfy two conditions: finite witnessability and smoothness.

  1. Finite witnessability ensures that if a formula is satisfiable, it can be satisfied by a model whose size is bounded by the number of variables in the formula.
  2. Smoothness ensures that if a formula is satisfied by a model of a certain size, it is also satisfied by any larger model.

While finite witnessability is often straightforward to prove, smoothness is notoriously difficult. As noted by Guilherme Toledo, Clark Barrett, and Yoni Zohar, the complexity of proving smoothness has historically acted as a barrier, preventing new theories from being integrated into solvers like cvc5 (Barbosa et al.).

Establishing Strong Politeness for Data Structures

A major milestone in this field was the formal proof that the theory of Algebraic Datatypes (ADTs)—the foundation for trees, lists, and records—is strongly polite. In Politeness for the Theory of Algebraic Datatypes, Ying Sheng, Jane Lange, and their colleagues established that ADTs can be safely combined with both infinite theories (like real arithmetic) and finite ones (like fixed-width bit-vectors).

To simplify this proof, the researchers utilized additive witness functions. Additivity provides a mechanical way to "upgrade" weak politeness to strong politeness, bypassing the manual, error-prone analysis of variable arrangements that previously plagued these proofs.

The Nonexistence of Unicorns

A central question in theory combination was whether smoothness was a truly independent requirement. Could a theory be stably infinite and finitely witnessable without being smooth? Such a theory was nicknamed a "unicorn"—a theoretical edge case that seemed possible but was never found.

In The Nonexistence of Unicorns and Many-Sorted Löwenheim-Skolem Theorems, Benjamin Przybocki, Guilherme V. Toledo, and their team proved that in many-sorted logic, these unicorns do not exist. They demonstrated that any theory that is both stably infinite and strongly finitely witnessable is automatically smooth.

This result is a significant simplification for the field. It means that researchers no longer need to struggle with the "notoriously difficult" smoothness property. Instead, they can rely on more accessible properties to guarantee that a theory is suitable for combination (Toledo et al.).

A Taxonomy of Combination Properties

Despite these simplifications, the relationship between different levels of politeness remains subtle. Ying Sheng and Christophe Ringeissen proved in Politeness and Stable Infiniteness: Stronger Together that "politeness" and "strong politeness" are indeed distinct properties. Relying on the weaker definition can lead to unsound results in SMT solvers when integrating non-stably infinite theories.

To provide a roadmap for future solver development, Guilherme V. Toledo and Clark Barrett have developed a systematic taxonomy of these model-theoretic properties (Combining Finite Combination Properties: Finite Models and Busy Beavers). By mapping every possible combination of smoothness, stable infiniteness, and convexity, they have defined the theoretical limits of how logical theories can—and cannot—be merged.

Papers in this version

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 8 papers
  2. Version 1 · 2026-10-04 · 16 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_polite_theory_combination_7ff9a9fb,
  title = {polite theory combination},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/polite-theory-combination/rdr_7ff9a9fbe780471697eb8ec2a0fade6e},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_polite_theory_combination_for_automated__7ff9a9fb_v1,
  title = {Polite Theory Combination for Automated Reasoning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/polite-theory-combination-for-automated-reasoning/rdr_7ff9a9fbe780471697eb8ec2a0fade6e/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}