Case Study: Saturations as Explicit Models in Equational Theories

Mikoláš Janota, Michael Rawson, Stephan Schulz · 2026

Read Case Study: Saturations as Explicit Models in Equational Theories by Mikoláš Janota, Michael Rawson, Stephan Schulz (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-16324.txt.

Description

Mikoláš Janota works with Michael Rawson and Stephan Schulz on a case study in automated theorem proving. Provers can refute a conjecture by saturating a set of clauses, but the saturated set that results is an opaque certificate, hard for a reader to interpret. In the unit equational fragment, the authors note, such a set can actually be read as a convergent rewrite system. That system defines an explicit model, possibly infinite. Yet this fact is little known even among frequent prover users.

The paper gives the certificate construction in full and builds it into the Vampire and E provers. It then applies the method to the Equational Theories Project, where hundreds of implications have no finite countermodel. Because the resulting rewrite systems can be checked for confluence and termination by existing certified tools, the construction yields countermodels that can be trusted rather than merely asserted.

Catalog record

CREATORMikoláš Janota, Michael Rawson, Stephan Schulz
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE20 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-16324

Browse the full library · About the Tower of Babel