State Canonization and Early Pruning in Width-Based Automated Theorem Proving
Mateus de Oliveira Oliveira, Sam Urmian · 2026
Read State Canonization and Early Pruning in Width-Based Automated Theorem Proving by Mateus de Oliveira Oliveira, Sam Urmian (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-2605-11025.txt.
Introduction
Mateus de Oliveira Oliveira and Sam Urmian advance width-based automated theorem proving with state canonization and early pruning. Width-based proving searches counterexamples width-wise against graph width measures like treewidth. Dynamic programming on tree decompositions can test long-standing graph conjectures in time doubly exponential in width.
State canonization cuts sharply the number of states checked during counterexample search, while early pruning fits conjectures of implication form where the antecedent is subgraph-closed. Applied to coloring conjectures for triangle-free graphs, the framework takes first practical steps toward viability testing. Theorem-proving researchers get two concrete techniques for taming width-based search.
Catalog record
| CREATOR | Mateus de Oliveira Oliveira, Sam Urmian |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 237803 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.11025