Clause splitting on non-Horn clauses is delegated to the AVATAR architecture [Vor14], backed by the CaDiCaL CDCL SAT solver. EPR-structured problems are handled lazily through AVATAR splitting rather than eager ground pre-expansion, which previously caused memory exhaustion on large Effectively Propositional problems.
Term retrieval for unification and matching uses perfect discrimination trees that track variable bindings through traversal [McC92], eliminating false-positive candidates at the index level. Subsumption and subsumption resolution are accelerated by Feature Vector Indexing [Sch04]. Redundancy elimination includes forward/backward demodulation, forward/backward subsumption, subsumption resolution, condensation, tautology deletion, and global subsumption with orphan elimination (removal of the entire derived subtree of a clause that is later found to be subsumed).
mrs runs a portfolio of independent search strategies concurrently on separate threads, one per available CPU core, each maintaining its own clause set; the first strategy to find a refutation signals the others to stop via a shared atomic flag. Strategies additionally share a pool of derived unit equalities across threads to accelerate sibling searches without duplicating work; each shared entry carries its full justifying ancestor chain back to the original problem's axioms, so a clause adopted from a sibling thread is spliced into the receiving thread's own proof record with a complete, locally self-consistent derivation rather than an opaque fact.
mrs is written entirely in Rust and does not depend on or invoke any external ATP system; all reasoning is performed in-process.
Each per-division priority order was derived empirically: every one of mrs's 15 base strategies (varying clause weight function, literal selection, term ordering, Set-of-Support depth, and AVATAR on/off) was run solo against a large corpus of representative FOF/UEQ problems at the official time limit, and a greedy set-cover algorithm selected the minimal-redundancy 8-strategy subset that maximizes problems solved when run in parallel. This tuning is strictly at the division level (FNE/FEQ/ UEQ), never at the level of individual problems or their solutions, and generalizes to unseen problems of the same syntactic class.
The baseline strategies use age-weight ratios (e.g. every 5th or 6th given-clause pick by FIFO age, the rest by weight) to balance breadth and depth of search, several distinct clause weight functions (including symbol-count, function-depth penalties, Horn-clause penalties, and conjecture-symbol boosting), and Set-of-Support restrictions that skip inferences between two clauses both far from the negated conjecture.
The FOF-to-CNF translation is fully documented in the proof output: each axiom or (negated) conjecture is cited as a leaf, followed by explicit fof_nnf_transformation and skolemisation (status esa) steps, and finally a cnf_transformation step that introduces the flat clauses used by the search — rather than citing the original problem file directly from the final clause. Negating the conjecture is likewise its own explicit step, annotated status cth with a single parent of role conjecture.
mrs is open source (MIT OR Apache-2.0) and available from:
https://github.com/newca12/mrs