code wiki / (root) / nx_subsumption.nx

nx_subsumption.nx

buildroot/runtime/nx_subsumption.nx

3534 B91 linesdepth 6pulls 6 transitivereach 19 importersview sourcekind library
docsdependenciesstructsconstsfunctions

about

nx_subsumption.nx -- forward subsumption for clause sets. Per Vampire-displacement roadmap Phase 1 step 2: clause C subsumes clause D iff there exists a substitution sigma such that for every literal Lc in C, there is a literal Ld in D with the same polarity AND Lc[sigma] = Ld. When C subsumes D, D is redundant and can be dropped from the passive set -- this is the single biggest pruner in saturation provers. Algorithm: backtracking match. For each literal of C in order, try every same-polarity literal of D as a match candidate. Snapshot substitution length before each attempt; on failure, roll back by resetting s.n. Subst bindings are append-only (see nx_unify), so truncating restores the prior state exactly. One-way matching (nx_match) is required, not full unification -- only C's variables get bound; D is treated as fixed. Bits-up nx_int, Result-typed errors via underlying primitives, scale-agnostic via nx_tier.

dependencies 6 imports · 18 importers

nx_syscalls.nx nx_runtime.nx nx_tier.nx nx_result.nx nx_unify.nx nx_resolution.nx nx_subsumption.nx nx_avatar_solve_test.nx nx_backward_subsume_test.nx nx_casc_bench.nx nx_casc_runner_test.nx nx_clause_weight_test.nx nx_discount_test.nx nx_fof_cnf_test.nx nx_fof_tseitin_test.nx nx_indexed_subsume_test.nx nx_pre_sat.nx

diagram shows first 10 each side; +0 more imports, +8 more importers in the complete lists below.

imports: nx_syscalls.nxnx_runtime.nxnx_tier.nxnx_result.nxnx_unify.nxnx_resolution.nx

imported by: nx_avatar_solve_test.nxnx_backward_subsume_test.nxnx_casc_bench.nxnx_casc_runner_test.nxnx_clause_weight_test.nxnx_discount_test.nxnx_fof_cnf_test.nxnx_fof_tseitin_test.nxnx_indexed_subsume_test.nxnx_pre_sat.nxnx_pre_sat_test.nxnx_saturation.nxnx_solve.nxnx_solve_test.nxnx_subsumption_test.nxnx_tptp_formula_test.nxnx_tptp_load_test.nxnx_tptp_write_test.nx

structs

none

consts

37const NX_SUBSUMES_YES: nx_int = 1
38const NX_SUBSUMES_NO: nx_int = 0

functions

42func nx_subsumes_from(c: *Clause, c_idx: nx_int,
76func nx_subsumes(c: *Clause, d: *Clause) -> nx_int
87func nx_subsumes_verdict_name(v: nx_int) -> *u8
called by 1: report