TSTP Solution File: SWV455+1 by Twee---2.5.0
View Problem
- Process Solution
%------------------------------------------------------------------------------
% File : Twee---2.5.0
% Problem : SWV455+1 : TPTP v8.2.0. Released v4.0.0.
% Transfm : none
% Format : tptp:raw
% Command : parallel-twee /export/starexec/sandbox/benchmark/theBenchmark.p --tstp --conditional-encoding if --smaller --drop-non-horn --give-up-on-saturation --explain-encoding
% Computer : n029.cluster.edu
% Model : x86_64 x86_64
% CPU : Intel(R) Xeon(R) CPU E5-2620 v4 2.10GHz
% Memory : 8042.1875MB
% OS : Linux 3.10.0-693.el7.x86_64
% CPULimit : 300s
% WCLimit : 300s
% DateTime : Mon Jun 24 17:32:13 EDT 2024
% Result : Theorem 7.67s 1.35s
% Output : Proof 8.00s
% Verified :
% SZS Type : -
% Comments :
%------------------------------------------------------------------------------
%----WARNING: Could not form TPTP format derivation
%------------------------------------------------------------------------------
%----ORIGINAL SYSTEM OUTPUT
% 0.03/0.13 % Problem : SWV455+1 : TPTP v8.2.0. Released v4.0.0.
% 0.03/0.13 % Command : parallel-twee /export/starexec/sandbox/benchmark/theBenchmark.p --tstp --conditional-encoding if --smaller --drop-non-horn --give-up-on-saturation --explain-encoding
% 0.12/0.34 % Computer : n029.cluster.edu
% 0.12/0.34 % Model : x86_64 x86_64
% 0.12/0.34 % CPU : Intel(R) Xeon(R) CPU E5-2620 v4 @ 2.10GHz
% 0.12/0.34 % Memory : 8042.1875MB
% 0.12/0.34 % OS : Linux 3.10.0-693.el7.x86_64
% 0.12/0.34 % CPULimit : 300
% 0.12/0.34 % WCLimit : 300
% 0.12/0.34 % DateTime : Thu Jun 20 14:43:39 EDT 2024
% 0.12/0.34 % CPUTime :
% 7.67/1.35 Command-line arguments: --no-flatten-goal
% 7.67/1.35
% 7.67/1.35 % SZS status Theorem
% 7.67/1.35
% 7.67/1.35 % SZS output start Proof
% 7.67/1.35 Take the following subset of the input axioms:
% 8.00/1.42 fof(axiom_46, axiom, ![Q, X, Y]: (elem(X, cons(Y, Q)) <=> (X=Y | elem(X, Q)))).
% 8.00/1.42 fof(conj, conjecture, ![X2, Y2, V, W]: ((![Z, Pid0]: (setIn(Pid0, alive) => ~elem(m_Down(Pid0), queue(host(Z)))) & (![Z2, Pid0_2]: (elem(m_Down(Pid0_2), queue(host(Z2))) => ~setIn(Pid0_2, alive)) & (![Z2, Pid0_2]: (elem(m_Down(Pid0_2), queue(host(Z2))) => host(Pid0_2)!=host(Z2)) & (![Z2, Pid0_2]: (elem(m_Halt(Pid0_2), queue(host(Z2))) => ~leq(host(Z2), host(Pid0_2))) & (![Pid20, Z2, Pid0_2]: (elem(m_Ack(Pid0_2, Z2), queue(host(Pid20))) => ~leq(host(Z2), host(Pid0_2))) & (![Z2, Pid0_2]: ((~setIn(Z2, alive) & (leq(Pid0_2, Z2) & host(Pid0_2)=host(Z2))) => ~setIn(Pid0_2, alive)) & (![Z2, Pid0_2]: ((Pid0_2!=Z2 & host(Pid0_2)=host(Z2)) => (~setIn(Z2, alive) | ~setIn(Pid0_2, alive))) & (![Pid30, Z2, Pid0_2, Pid20_2]: ((host(Pid20_2)!=host(Z2) & (setIn(Z2, alive) & (setIn(Pid20_2, alive) & (host(Pid30)=host(Z2) & host(Pid0_2)=host(Pid20_2))))) => ~(elem(m_Down(Pid0_2), queue(host(Z2))) & elem(m_Down(Pid30), queue(host(Pid20_2))))) & queue(host(X2))=cons(m_Down(Y2), V))))))))) => (setIn(X2, alive) => (~leq(host(X2), host(Y2)) => (~((index(ldr, host(X2))=host(Y2) & index(status, host(X2))=norm) | (index(status, host(X2))=wait & host(Y2)=host(index(elid, host(X2))))) => (~(![Z2]: ((~leq(host(X2), Z2) & leq(s(zero), Z2)) => (setIn(Z2, index(down, host(X2))) | Z2=host(Y2))) & index(status, host(X2))=elec_1) => ![Z2]: (host(X2)!=host(Z2) => ![W0, X0]: (host(X2)=host(X0) => ![Y0]: ((host(X0)!=host(Z2) & (setIn(Z2, alive) & (setIn(X0, alive) & (host(W0)=host(Z2) & host(Y0)=host(X0))))) => ~(elem(m_Down(W0), V) & elem(m_Down(Y0), queue(host(Z2))))))))))))).
% 8.00/1.42
% 8.00/1.42 Now clausify the problem and encode Horn clauses using encoding 3 of
% 8.00/1.42 http://www.cse.chalmers.se/~nicsma/papers/horn.pdf.
% 8.00/1.42 We repeatedly replace C & s=t => u=v by the two clauses:
% 8.00/1.42 fresh(y, y, x1...xn) = u
% 8.00/1.42 C => fresh(s, t, x1...xn) = v
% 8.00/1.42 where fresh is a fresh function symbol and x1..xn are the free
% 8.00/1.42 variables of u and v.
% 8.00/1.42 A predicate p(X) is encoded as p(X)=true (this is sound, because the
% 8.00/1.42 input problem has no model of domain size 1).
% 8.00/1.42
% 8.00/1.42 The encoding turns the above axioms into the following unit equations and goals:
% 8.00/1.42
% 8.00/1.42 Axiom 1 (conj_3): host(y0) = host(x0).
% 8.00/1.42 Axiom 2 (conj_2): host(w0) = host(z2).
% 8.00/1.42 Axiom 3 (conj_1): host(x) = host(x0).
% 8.00/1.42 Axiom 4 (conj_8): setIn(x0, alive) = true2.
% 8.00/1.42 Axiom 5 (conj_7): setIn(z2, alive) = true2.
% 8.00/1.42 Axiom 6 (conj): queue(host(x)) = cons(m_Down(y), v).
% 8.00/1.42 Axiom 7 (conj_4): elem(m_Down(w0), v) = true2.
% 8.00/1.42 Axiom 8 (conj_12): fresh41(X, X, Y, Z) = host(Y).
% 8.00/1.42 Axiom 9 (conj_12): fresh39(X, X, Y, Z, W) = host(W).
% 8.00/1.42 Axiom 10 (axiom_46_1): fresh33(X, X, Y, Z, W) = true2.
% 8.00/1.42 Axiom 11 (conj_5): elem(m_Down(y0), queue(host(z2))) = true2.
% 8.00/1.42 Axiom 12 (conj_12): fresh40(X, X, Y, Z, W, V) = fresh41(host(Z), host(Y), Y, W).
% 8.00/1.42 Axiom 13 (conj_12): fresh38(X, X, Y, Z, W, V) = fresh39(host(V), host(W), Y, Z, W).
% 8.00/1.42 Axiom 14 (axiom_46_1): fresh33(elem(X, Y), true2, X, Z, Y) = elem(X, cons(Z, Y)).
% 8.00/1.42 Axiom 15 (conj_12): fresh36(X, X, Y, Z, W, V) = fresh37(setIn(Y, alive), true2, Y, Z, W, V).
% 8.00/1.42 Axiom 16 (conj_12): fresh37(X, X, Y, Z, W, V) = fresh40(elem(m_Down(Z), queue(host(W))), true2, Y, Z, W, V).
% 8.00/1.42 Axiom 17 (conj_12): fresh36(setIn(X, alive), true2, Y, Z, X, W) = fresh38(elem(m_Down(W), queue(host(Y))), true2, Y, Z, X, W).
% 8.00/1.42
% 8.00/1.42 Lemma 18: host(x) = host(y0).
% 8.00/1.42 Proof:
% 8.00/1.42 host(x)
% 8.00/1.42 = { by axiom 3 (conj_1) }
% 8.00/1.42 host(x0)
% 8.00/1.42 = { by axiom 1 (conj_3) R->L }
% 8.00/1.42 host(y0)
% 8.00/1.42
% 8.00/1.42 Lemma 19: host(y0) = host(w0).
% 8.00/1.42 Proof:
% 8.00/1.42 host(y0)
% 8.00/1.42 = { by axiom 1 (conj_3) }
% 8.00/1.42 host(x0)
% 8.00/1.42 = { by axiom 8 (conj_12) R->L }
% 8.00/1.42 fresh41(host(y0), host(y0), x0, z2)
% 8.00/1.42 = { by axiom 1 (conj_3) }
% 8.00/1.42 fresh41(host(y0), host(x0), x0, z2)
% 8.00/1.42 = { by axiom 12 (conj_12) R->L }
% 8.00/1.42 fresh40(true2, true2, x0, y0, z2, w0)
% 8.00/1.42 = { by axiom 11 (conj_5) R->L }
% 8.00/1.42 fresh40(elem(m_Down(y0), queue(host(z2))), true2, x0, y0, z2, w0)
% 8.00/1.42 = { by axiom 16 (conj_12) R->L }
% 8.00/1.42 fresh37(true2, true2, x0, y0, z2, w0)
% 8.00/1.42 = { by axiom 4 (conj_8) R->L }
% 8.00/1.42 fresh37(setIn(x0, alive), true2, x0, y0, z2, w0)
% 8.00/1.42 = { by axiom 15 (conj_12) R->L }
% 8.00/1.42 fresh36(true2, true2, x0, y0, z2, w0)
% 8.00/1.42 = { by axiom 5 (conj_7) R->L }
% 8.00/1.42 fresh36(setIn(z2, alive), true2, x0, y0, z2, w0)
% 8.00/1.42 = { by axiom 17 (conj_12) }
% 8.00/1.42 fresh38(elem(m_Down(w0), queue(host(x0))), true2, x0, y0, z2, w0)
% 8.00/1.42 = { by axiom 1 (conj_3) R->L }
% 8.00/1.42 fresh38(elem(m_Down(w0), queue(host(y0))), true2, x0, y0, z2, w0)
% 8.00/1.42 = { by lemma 18 R->L }
% 8.00/1.42 fresh38(elem(m_Down(w0), queue(host(x))), true2, x0, y0, z2, w0)
% 8.00/1.42 = { by axiom 6 (conj) }
% 8.00/1.42 fresh38(elem(m_Down(w0), cons(m_Down(y), v)), true2, x0, y0, z2, w0)
% 8.00/1.42 = { by axiom 14 (axiom_46_1) R->L }
% 8.00/1.42 fresh38(fresh33(elem(m_Down(w0), v), true2, m_Down(w0), m_Down(y), v), true2, x0, y0, z2, w0)
% 8.00/1.42 = { by axiom 7 (conj_4) }
% 8.00/1.42 fresh38(fresh33(true2, true2, m_Down(w0), m_Down(y), v), true2, x0, y0, z2, w0)
% 8.00/1.42 = { by axiom 10 (axiom_46_1) }
% 8.00/1.42 fresh38(true2, true2, x0, y0, z2, w0)
% 8.00/1.42 = { by axiom 13 (conj_12) }
% 8.00/1.42 fresh39(host(w0), host(z2), x0, y0, z2)
% 8.00/1.42 = { by axiom 2 (conj_2) }
% 8.00/1.42 fresh39(host(z2), host(z2), x0, y0, z2)
% 8.00/1.42 = { by axiom 9 (conj_12) }
% 8.00/1.43 host(z2)
% 8.00/1.43 = { by axiom 2 (conj_2) R->L }
% 8.00/1.43 host(w0)
% 8.00/1.43
% 8.00/1.43 Goal 1 (conj_17): host(x0) = host(z2).
% 8.00/1.43 Proof:
% 8.00/1.43 host(x0)
% 8.00/1.43 = { by axiom 1 (conj_3) R->L }
% 8.00/1.43 host(y0)
% 8.00/1.43 = { by lemma 19 }
% 8.00/1.43 host(w0)
% 8.00/1.43 = { by axiom 2 (conj_2) }
% 8.00/1.43 host(z2)
% 8.00/1.43
% 8.00/1.43 Goal 2 (conj_14): host(x) = host(z2).
% 8.00/1.43 Proof:
% 8.00/1.43 host(x)
% 8.00/1.43 = { by lemma 18 }
% 8.00/1.43 host(y0)
% 8.00/1.43 = { by lemma 19 }
% 8.00/1.43 host(w0)
% 8.00/1.43 = { by axiom 2 (conj_2) }
% 8.00/1.43 host(z2)
% 8.00/1.43 % SZS output end Proof
% 8.00/1.43
% 8.00/1.43 RESULT: Theorem (the conjecture is true).
%------------------------------------------------------------------------------