CNF Encoded Isomorphic and Optimized Miters from Hardware Model Checking Competition 2012 Models

<p>These miter benchmarks are used in a paper on congruence closure in 2024.</p> <p>The miter AIGs in the [`aig`](aig) directory are the same as those used to<br>generate CNFs of miter benchmarks submitted to the SAT Challenge in 2012.<br>Some of them have regularly been used in the SAT Competitions since then.</p> <p>The AIGs are separated into two sets:</p> <p>- [`aig/iso`](aig/iso) miters of isomorphic circuits<br>- [`aig/opt`](aig/opt) miters of optimized versus original circuit</p> <p>The first set checks equivalence of one circuit with itself in the<br>[`aig/iso`](aig/iso) (isomorphic) sub-directory and second set contains<br>equivalence checking problems (aka miters) comparing the original circuit<br>with an optimized version in the [`aig/opt`](aig/opt) (optimized)<br>sub-directory. &nbsp;The optimized versions of the circuits were obtained in 2012<br>by the `dc2` script for [ABC](https://people.eecs.berkeley.edu/~alanmi/abc).<br>We did not re-run ABC with a newer version in order to make sure we have as<br>base-line in our experiments the same CNFs, as they are well-known, i.e.,&nbsp;<br>they have been used in the SAT competitions for several years.</p> <p>Note that the original AIGER models have state elements (called "latches"<br>in AIGER terminology), but both the optimization with ABC as well as our<br>equivalence checking is purely combinational, by treating latches as<br>additional pseudo inputs, and next-state functions as output-functions. &nbsp;The<br>miters were accordingly generated (by the 2011 version) of `aigmiter` using<br>the `-c` option. &nbsp;For the same reason as for ABC explained above, we did not<br>rerun `aigmiter` either.</p> <p>We then encoded the two sets of AIGs into CNF in two different ways.<br>The first encoding just uses a simple Tseitin encoding, without<br>Plaisted-Greenbaum optimization, i.e., using the `--no-pg` option, as in 2012.<br>Even though we use a new version of `aigtocnf` in `src/aiger/aigtocnf.c` we<br>made sure that identical CNFs are generated for this first encoding variant<br>by checking that the MD5 sum of the (actually compressed) CNF files match.<br>This required to disable a newly introduced cone-of-influence (COI)<br>optimization with `--no-coi` which skips unreachable gates even when the<br>Plaisted-Greenbaum optimization is disabled.</p> <p>The second variant of the encoding detects XOR and ITE gates by pattern<br>matching and produces more concise CNFs by skipping internal AND gates<br>of detected XOR and ITE gates producing a direct encoding instead.</p> <p>This gives the following sets of CNFs;</p> <p>- [`cnf/ands/iso`](cnf/ands/iso) isomorphic circuits with ANDs only<br>- [`cnf/ands/opt`](cnf/ands/opt) optimized versus original with ANDs only<br>- [`cnf/xits/iso`](cnf/xits/isor) isomorphic circuits with ANDs, XORs, ITEs<br>- [`cnf/xits/opt`](cnf/xits/opt) optimized versus original with ANDs, XORs, ITEs</p> <p>All the CNFs in these directories have the same original file name of the<br>AIGER model to simplify run-time comparison. &nbsp;In `cnf/all` we further<br>provide links with qualified names to distinguish them.</p>