Proof step 1 from proof k-reachable-def (conclusion) (back to tree)

System applied rule normalize

And obtained the following new goals

• Proof step 2:

  ¬(reachable(r, r0, h) ↔ r ≠ null ∧ r ∈ h ∧ reachable*(h, r, r0)) ⊦

Rule argument

Additional information

Proof step 2 from proof k-reachable-def (previous step) (back to tree)

User applied rule apply rewrite lemma

And obtained the following new goals

• Proof step 3:

  ⊦ reachable(r, r0, h) ↔ (∃ x. path(r ' + x, h) ∧ (r ' + x).last = r0)

• Proof step 4:

  ⊦ (∃ x. path(r ' + x, h) ∧ (r ' + x).last = r0) ↔ r ≠ null ∧ r ∈ h ∧ reachable*(h, r, r0)

Rule argument

Additional information

Used terms: h, r0, r

Proof step 3 from proof k-reachable-def (previous step) (back to tree)

Lemma reachable-def

Proof step 4 from proof k-reachable-def (previous step) (back to tree)

User applied rule apply rewrite lemma

And obtained the following new goals

• Proof step 5:

  ⊦ reachable*(h, r, r0) ↔ (∃ n. reachable-n(h, n, r, r0))

• Proof step 6:

  ⊦ (∃ x. path(r ' + x, h) ∧ (r ' + x).last = r0) ↔ r ≠ null ∧ r ∈ h ∧ (∃ n. reachable-n(h, n, r, r0))

Rule argument

Additional information

Used terms: r0, r, h

Proof step 5 from proof k-reachable-def (previous step) (back to tree)

Lemma reachable-star-def

Proof step 6 from proof k-reachable-def (previous step) (back to tree)

User applied rule case distinction

And obtained the following new goals

• Proof step 7:

  ∃ x. path(r ' + x, h) ∧ (r ' + x).last = r0 ⊦ r ≠ null ∧ r ∈ h ∧ (∃ n. reachable-n(h, n, r, r0))

• Proof step 27:

  r ≠ null, r ∈ h, ∃ n. reachable-n(h, n, r, r0) ⊦ ∃ x. path(r ' + x, h) ∧ (r ' + x).last = r0

Rule argument

Additional information

Proof step 7 from proof k-reachable-def (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 8:

  r ≠ null, path(r ' + x, h) ⊦ ∃ n. reachable-n(h, n, r, (r ' + x).last)

Rule argument

Additional information

Used simplifier rules: path-first-in-H: ⊦ path(r ' + x, h) → (r ∈ h ↔ true); null-not-start-of-path: ⊦ ¬ path(null ' + x, h); a: ⊦ (x + y) + z = x + y + z; from specification polylist

Proof step 8 from proof k-reachable-def (previous step) (back to tree)

Heuristic weak cut applied rule cut formula

And obtained the following new goals

• Proof step 9:

  x = [], r ≠ null, path(r ' + x, h) ⊦ ∃ n. reachable-n(h, n, r, (r ' + x).last)

• Proof step 11:

  r ≠ null, x ≠ [], path(r ' + x, h) ⊦ ∃ n. reachable-n(h, n, r, (r ' + x).last)

Rule argument

Additional information

Used formulas: x = []

Proof step 9 from proof k-reachable-def (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 10:

  r ≠ null, r ∈ h ⊦ ∃ n. reachable-n(h, n, r, r)

Rule argument

Additional information

Used simplifier rules: path-one: ⊦ path(r ', h) ↔ r ∈ h ∧ r ≠ null; ⊦ a '.last = a; (s) a: ⊦ (x + y) + z = x + y + z; from specification polylist ⊦ x + [] = x; (s)

Proof step 10 from proof k-reachable-def (previous step) (back to tree)

User applied rule exists right

And closed the goal!

Rule argument

Additional information

Used simplifier rules: reachable-n-base: ⊦ reachable-n(h, 0, r, r0) ↔ r = r0; Used terms: 0

Proof step 11 from proof k-reachable-def (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 12:

  r ≠ null, x ≠ [], path(r ' + x, h) ⊦ ∃ n. reachable-n(h, n, r, x.last)

Rule argument

Additional information

Used simplifier rules: a: ⊦ (x + y) + z = x + y + z; from specification polylist ⊦ y ≠ [] → (x + y).last = y.last; (s)

Proof step 12 from proof k-reachable-def (previous step) (back to tree)

User applied rule structural induction

And obtained the following new goals

• Proof step 13:

  r0 + x0 ≠ [], r ≠ null, path(r ' + (r0 + x0), h), ∀ r, h. r ≠ null ∧ x0 ≠ [] ∧ path(r ' + x0, h) → (∃ n. reachable-n(h, n, r, x0.last)) ⊦ ∃ n. reachable-n(h, n, r, (r0 + x0).last)

Rule argument

Additional information

Used simplifier rules: list('a) freely generated by [], +;;

Proof step 13 from proof k-reachable-def (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 14:

  r ≠ null, path(h[r].nxt ' + x0, h), r ∈ h, ∀ r, h. r ≠ null ∧ x0 ≠ [] ∧ path(r ' + x0, h) → (∃ n. reachable-n(h, n, r, x0.last)) ⊦ ∃ n. reachable-n(h, n, r, (h[r].nxt ' + x0).last)

Rule argument

Additional information

Used simplifier rules: path-cons: ⊦ path(r ' + r0 ' + x, h) ↔ r ∈ h ∧ r ≠ null ∧ h[r].nxt = r0 ∧ path(r0 ' + x, h); ⊦ a + x = a ' + x; (s) a: ⊦ (x + y) + z = x + y + z; from specification polylist ⊦ a ' + x ≠ []; (s)

Proof step 14 from proof k-reachable-def (previous step) (back to tree)

Heuristic weak cut applied rule cut formula

And obtained the following new goals

• Proof step 15:

  x0 = [], r ≠ null, path(h[r].nxt ' + x0, h), r ∈ h, ∀ r, h. r ≠ null ∧ x0 ≠ [] ∧ path(r ' + x0, h) → (∃ n. reachable-n(h, n, r, x0.last)) ⊦ ∃ n. reachable-n(h, n, r, (h[r].nxt ' + x0).last)

• Proof step 17:

  r ≠ null, x0 ≠ [], path(h[r].nxt ' + x0, h), r ∈ h, ∀ r, h. r ≠ null ∧ x0 ≠ [] ∧ path(r ' + x0, h) → (∃ n. reachable-n(h, n, r, x0.last)) ⊦ ∃ n. reachable-n(h, n, r, (h[r].nxt ' + x0).last)

Rule argument

Additional information

Used formulas: x0 = []

Proof step 15 from proof k-reachable-def (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 16:

  h[r].nxt ≠ null, r ≠ null, r ∈ h, h[r].nxt ∈ h ⊦ ∃ n. reachable-n(h, n, r, h[r].nxt)

Rule argument

Additional information

Used simplifier rules: path-one: ⊦ path(r ', h) ↔ r ∈ h ∧ r ≠ null; ⊦ a '.last = a; (s) a: ⊦ (x + y) + z = x + y + z; from specification polylist ⊦ x + [] = x; (s)

Proof step 16 from proof k-reachable-def (previous step) (back to tree)

User applied rule exists right

And closed the goal!

Rule argument

Additional information

Used simplifier rules: reachable-n-1: ⊦ reachable-n(h, 1, r, r0) ↔ reachable-1(h, r, r0); reachable-1-def: ⊦ reachable-1(h, r, r0) ↔ r ≠ null ∧ r0 ≠ null ∧ r ∈ h ∧ r0 ∈ h ∧ h[r].nxt = r0; Used terms: 0 +1

Proof step 17 from proof k-reachable-def (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 18:

  r ≠ null, x0 ≠ [], path(h[r].nxt ' + x0, h), r ∈ h, ∀ r0, h0. r0 ≠ null ∧ path(r0 ' + x0, h0) → (∃ n. reachable-n(h0, n, r0, x0.last)) ⊦ ∃ n. reachable-n(h, n, r, x0.last)

Rule argument

Additional information

Used simplifier rules: a: ⊦ (x + y) + z = x + y + z; from specification polylist ⊦ y ≠ [] → (x + y).last = y.last; (s)

Proof step 18 from proof k-reachable-def (previous step) (back to tree)

User applied rule all left

And obtained the following new goals

• Proof step 19:

  r ≠ null, x0 ≠ [], path(h[r].nxt ' + x0, h), r ∈ h, h[r].nxt ≠ null ∧ path(h[r].nxt ' + x0, h) → (∃ n. reachable-n(h, n, h[r].nxt, x0.last)) ⊦ ∃ n. reachable-n(h, n, r, x0.last)

Rule argument

Additional information

Used terms: h[r].nxt, h

Proof step 19 from proof k-reachable-def (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 20:

  r ≠ null, x0 ≠ [], path(h[r].nxt ' + x0, h), r ∈ h, h[r].nxt ≠ null → reachable-n(h, n, h[r].nxt, x0.last) ⊦ ∃ n. reachable-n(h, n, r, x0.last)

Rule argument

Additional information

Proof step 20 from proof k-reachable-def (previous step) (back to tree)

User applied rule exists right

And obtained the following new goals

• Proof step 21:

  r ≠ null, x0 ≠ [], path(h[r].nxt ' + x0, h), r ∈ h, ¬ reachable-n(h, n +1, r, x0.last), h[r].nxt ≠ null → reachable-n(h, n, h[r].nxt, x0.last) ⊦

Rule argument

Additional information

Used terms: n +1

Proof step 21 from proof k-reachable-def (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 22:

  r ≠ null, x0 ≠ [], path(h[r].nxt ' + x0, h), r ∈ h, h[r].nxt ≠ null → reachable-n(h, n, h[r].nxt, x0.last) ⊦ ∃ r1. reachable-1(h, r, r1) ∧ reachable-n(h, n, r1, x0.last)

Rule argument

Additional information

Used simplifier rules: reachable-n-rec: ⊦ reachable-n(h, n + 1, r, r0) ↔ (∃ r1. reachable-1(h, r, r1) ∧ reachable-n(h, n, r1, r0)); c: ⊦ m + n = n + m; from specification nat-basic a: ⊦ (m + n0) + n1 = m + n0 + n1; from specification nat-basic ⊦ m +1 = m + 1; (s)

Proof step 22 from proof k-reachable-def (previous step) (back to tree)

User applied rule exists right

And obtained the following new goals

• Proof step 23:

  r ≠ null, x0 ≠ [], path(h[r].nxt ' + x0, h), r ∈ h, h[r].nxt ≠ null → reachable-n(h, n, h[r].nxt, x0.last) ⊦ reachable-1(h, r, h[r].nxt) ∧ reachable-n(h, n, h[r].nxt, x0.last)

Rule argument

Additional information

Used terms: h[r].nxt

Proof step 23 from proof k-reachable-def (previous step) (back to tree)

User applied rule apply rewrite lemma

And obtained the following new goals

• Proof step 24:

  ⊦ reachable-1(h, r, r0) ↔ r ≠ null ∧ r0 ≠ null ∧ r ∈ h ∧ r0 ∈ h ∧ h[r].nxt = r0

• Proof step 25:

  r ≠ null, x0 ≠ [], path(h[r].nxt ' + x0, h), r ∈ h, h[r].nxt ≠ null → reachable-n(h, n, h[r].nxt, x0.last) ⊦ (r ≠ null ∧ h[r].nxt ≠ null ∧ r ∈ h ∧ h[r].nxt ∈ h ∧ h[r].nxt = h[r].nxt) ∧ reachable-n(h, n, h[r].nxt, x0.last)

Rule argument

Additional information

Used terms: h, r, h[r].nxt

Proof step 24 from proof k-reachable-def (previous step) (back to tree)

Lemma reachable-1-def

Proof step 25 from proof k-reachable-def (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 26:

  r ≠ null, x0 ≠ [], path(h[r].nxt ' + x0, h), r ∈ h, h[r].nxt ≠ null → reachable-n(h, n, h[r].nxt, x0.last) ⊦ h[r].nxt ≠ null ∧ reachable-n(h, n, h[r].nxt, x0.last)

Rule argument

Additional information

Used simplifier rules: path-first-in-H: ⊦ path(r ' + x, h) → (r ∈ h ↔ true); a: ⊦ (x + y) + z = x + y + z; from specification polylist

Proof step 26 from proof k-reachable-def (previous step) (back to tree)

User applied rule case distinction

And closed the goal!

Rule argument

Additional information

Used simplifier rules: null-not-start-of-path: ⊦ ¬ path(null ' + x, h); null-not-start-of-path: ⊦ ¬ path(null ' + x, h); a: ⊦ (x + y) + z = x + y + z; from specification polylist

Proof step 27 from proof k-reachable-def (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 28:

  r ≠ null, reachable-n(h, n, r, r0), r ∈ h ⊦ ∃ x. path(r ' + x, h) ∧ (r ' + x).last = r0

Rule argument

Additional information

Proof step 28 from proof k-reachable-def (previous step) (back to tree)

User applied rule cut formula

And obtained the following new goals

• Proof step 29:

  n = 0, r ≠ null, reachable-n(h, n, r, r0), r ∈ h ⊦ ∃ x. path(r ' + x, h) ∧ (r ' + x).last = r0

• Proof step 31:

  n ≠ 0, r ≠ null, reachable-n(h, n, r, r0), r ∈ h ⊦ ∃ x. path(r ' + x, h) ∧ (r ' + x).last = r0

Rule argument

Additional information

Used formulas: n = 0

Proof step 29 from proof k-reachable-def (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 30:

  r0 ≠ null, r0 ∈ h ⊦ ∃ x. path(r0 ' + x, h) ∧ (r0 ' + x).last = r0

Rule argument

Additional information

Used simplifier rules: reachable-n-base: ⊦ reachable-n(h, 0, r, r0) ↔ r = r0;

Proof step 30 from proof k-reachable-def (previous step) (back to tree)

User applied rule exists right

And closed the goal!

Rule argument

Additional information

Used simplifier rules: path-one: ⊦ path(r ', h) ↔ r ∈ h ∧ r ≠ null; ⊦ x + [] = x; (s) a: ⊦ (x + y) + z = x + y + z; from specification polylist ⊦ a '.last = a; (s) Used terms: []

Proof step 31 from proof k-reachable-def (previous step) (back to tree)

User applied rule structural induction

And obtained the following new goals

• Proof step 32:

  n0 +1 ≠ 0, r ≠ null, reachable-n(h, n0 +1, r, r0), r ∈ h, ∀ r, h, r0. n0 ≠ 0 ∧ r ≠ null ∧ reachable-n(h, n0, r, r0) ∧ r ∈ h → (∃ x. path(r ' + x, h) ∧ (r ' + x).last = r0) ⊦ ∃ x. path(r ' + x, h) ∧ (r ' + x).last = r0

Rule argument

Additional information

Used simplifier rules: nat freely generated by 0, +1;;

Proof step 32 from proof k-reachable-def (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 33:

  h[r].nxt ≠ null, r ≠ null, reachable-n(h, n0, h[r].nxt, r0), h[r].nxt ∈ h, r ∈ h, ∀ r, h, r0. n0 ≠ 0 ∧ r ≠ null ∧ reachable-n(h, n0, r, r0) ∧ r ∈ h → (∃ x. path(r ' + x, h) ∧ (r ' + x).last = r0) ⊦ ∃ x. path(r ' + x, h) ∧ (r ' + x).last = r0

Rule argument

Additional information

Used simplifier rules: reachable-n-rec: ⊦ reachable-n(h, n + 1, r, r0) ↔ (∃ r1. reachable-1(h, r, r1) ∧ reachable-n(h, n, r1, r0)); reachable-1-def: ⊦ reachable-1(h, r, r0) ↔ r ≠ null ∧ r0 ≠ null ∧ r ∈ h ∧ r0 ∈ h ∧ h[r].nxt = r0; c: ⊦ m + n = n + m; from specification nat-basic a: ⊦ (m + n0) + n1 = m + n0 + n1; from specification nat-basic ⊦ m +1 = m + 1; (s) ⊦ m + 1 ≠ 0; (s)

Proof step 33 from proof k-reachable-def (previous step) (back to tree)

User applied rule all left

And obtained the following new goals

• Proof step 34:

  h[r].nxt ≠ null, r ≠ null, reachable-n(h, n0, h[r].nxt, r0), r ∈ h, h[r].nxt ∈ h, n0 ≠ 0 ∧ h[r].nxt ≠ null ∧ reachable-n(h, n0, h[r].nxt, r0) ∧ h[r].nxt ∈ h → (∃ x. path(h[r].nxt ' + x, h) ∧ (h[r].nxt ' + x).last = r0) ⊦ ∃ x. path(r ' + x, h) ∧ (r ' + x).last = r0

Rule argument

Additional information

Used terms: h[r].nxt, h, r0

Proof step 34 from proof k-reachable-def (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 35:

  h[r].nxt ≠ null, r ≠ null, reachable-n(h, n0, h[r].nxt, r0), h[r].nxt ∈ h, r ∈ h, n0 ≠ 0 → path(h[r].nxt ' + x, h) ∧ (h[r].nxt ' + x).last = r0 ⊦ ∃ x. path(r ' + x, h) ∧ (r ' + x).last = r0

Rule argument

Additional information

Proof step 35 from proof k-reachable-def (previous step) (back to tree)

User applied rule cut formula

And obtained the following new goals

• Proof step 36:

  n0 = 0, h[r].nxt ≠ null, r ≠ null, reachable-n(h, n0, h[r].nxt, r0), r ∈ h, h[r].nxt ∈ h, n0 ≠ 0 → path(h[r].nxt ' + x, h) ∧ (h[r].nxt ' + x).last = r0 ⊦ ∃ x. path(r ' + x, h) ∧ (r ' + x).last = r0

• Proof step 38:

  h[r].nxt ≠ null, n0 ≠ 0, r ≠ null, reachable-n(h, n0, h[r].nxt, r0), r ∈ h, h[r].nxt ∈ h, n0 ≠ 0 → path(h[r].nxt ' + x, h) ∧ (h[r].nxt ' + x).last = r0 ⊦ ∃ x. path(r ' + x, h) ∧ (r ' + x).last = r0

Rule argument

Additional information

Used formulas: n0 = 0

Proof step 36 from proof k-reachable-def (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 37:

  h[r].nxt ≠ null, r ≠ null, r ∈ h, h[r].nxt ∈ h ⊦ ∃ x. path(r ' + x, h) ∧ (r ' + x).last = h[r].nxt

Rule argument

Additional information

Used simplifier rules: reachable-n-base: ⊦ reachable-n(h, 0, r, r0) ↔ r = r0;

Proof step 37 from proof k-reachable-def (previous step) (back to tree)

User applied rule exists right

And closed the goal!

Rule argument

Additional information

Used simplifier rules: path-two: ⊦ path(r ' + r0 ', h) ↔ r ∈ h ∧ r0 ∈ h ∧ r ≠ null ∧ r0 ≠ null ∧ h[r].nxt = r0; ⊦ (x + a ').last = a; (s) a: ⊦ (x + y) + z = x + y + z; from specification polylist Used terms: h[r].nxt '

Proof step 38 from proof k-reachable-def (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 39:

  h[r].nxt ≠ null, n0 ≠ 0, r ≠ null, path(h[r].nxt ' + x, h), reachable-n(h, n0, h[r].nxt, (h[r].nxt ' + x).last), r ∈ h, h[r].nxt ∈ h ⊦ ∃ x0. path(r ' + x0, h) ∧ (r ' + x0).last = (h[r].nxt ' + x).last

Rule argument

Additional information

Proof step 39 from proof k-reachable-def (previous step) (back to tree)

User applied rule exists right

And closed the goal!

Rule argument

Additional information

Used simplifier rules: path-cons: ⊦ path(r ' + r0 ' + x, h) ↔ r ∈ h ∧ r ≠ null ∧ h[r].nxt = r0 ∧ path(r0 ' + x, h); ⊦ (x + a ' + y).last = (a ' + y).last; (s) a: ⊦ (x + y) + z = x + y + z; from specification polylist Used terms: h[r].nxt ' + x