Term Ordering Diagrams
Márton Hajdu (✉), Robin Coutelier, Laura Kovács, Andrei Voronkov · 2025
Read Term Ordering Diagrams by Márton Hajdu (✉), Robin Coutelier, Laura Kovács, Andrei Voronkov (2025) 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-2505-22181.txt.
Description
Automated theorem provers spend most of their time comparing terms, and a 2025 arXiv paper by Márton Hajdu and co-authors builds an index to stop the repetition. The ordering checks guide which clauses a prover may simplify, and the same unorderable pairs come up again and again after substitutions.
Their data structure, the term ordering diagram, stores earlier checks lazily and reuses them as substitutions land. In experiments the ordering step had eaten up to 98 percent of proving time on hard examples, which is the waste the index attacks. The authors report the speedups across their test set.
Catalog record
| CREATOR | Márton Hajdu (✉), Robin Coutelier, Laura Kovács, Andrei Voronkov |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 101 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-22181