Proof step 1 from proof lst-in-hp (conclusion) (back to tree)

System applied rule normalize

And obtained the following new goals

• Proof step 2:

  r ≠ null, (o[lst(r)] * hR)[rs, cf, af], ¬ r ∈ rs ⊦

Rule argument

Additional information

Proof step 2 from proof lst-in-hp (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 3:

  r ≠ null, (o[_∃(λ x. ls(r, x))] * hR)[rs, cf, af], ¬ r ∈ rs ⊦

Rule argument

Additional information

Used simplifier rules: lst-rec: ⊦ r ≠ null → lst(r) = _∃(λ x. ls(r, x));

Proof step 3 from proof lst-in-hp (previous step) (back to tree)

User applied rule apply rewrite lemma

And obtained the following new goals

• Proof step 4:

  ⊦ (o[_∃ xv] * hR)[rs, cf, af] ↔ (∃ x. (o[xv(x)] * hR)[rs, cf, af])

• Proof step 5:

  r ≠ null, ¬ r ∈ rs, ∃ x. (o[ls(r, x)] * hR)[rs, cf, af] ⊦

Rule argument

Additional information

Used terms: hR, cf, λ x. ls(r, x), rs, af, o

Proof step 4 from proof lst-in-hp (previous step) (back to tree)

Lemma ex-lst-shift

Proof step 5 from proof lst-in-hp (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 6:

  r ≠ null, (o[ls(r, x)] * hR)[rs, cf, af], ¬ r ∈ rs ⊦

Rule argument

Additional information

Proof step 6 from proof lst-in-hp (previous step) (back to tree)

User applied rule apply rewrite lemma

And obtained the following new goals

• Proof step 7:

  ⊦ (hR0 * hR1)[rs, f, g] ↔ (∃ rs0, rs1. rs0 ∪ rs1 = rs ∧ rs0 ∩ rs1 = ∅ ∧ hR0[rs0, f, g] ∧ hR1[rs1, f, g])

• Proof step 8:

  r ≠ null, ¬ r ∈ rs, ∃ rs0, rs1. rs0 ∪ rs1 = rs ∧ rs0 ∩ rs1 = ∅ ∧ o[ls(r, x)][rs0, cf, af] ∧ hR[rs1, cf, af] ⊦

Rule argument

Additional information

Used terms: cf, rs, hR, af, o[ls(r, x)]

Proof step 7 from proof lst-in-hp (previous step) (back to tree)

A spec-lemma

Proof step 8 from proof lst-in-hp (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 9:

  rs0 ∩ rs1 = ∅, r ≠ null, o[ls(r, x)][rs0, cf, af], hR[rs1, cf, af], ¬ r ∈ rs0, ¬ r ∈ rs1 ⊦

Rule argument

Additional information

Used simplifier rules: unc: ⊦ s ∪ s0 = s0 ∪ s; from specification set-union[refset] una: ⊦ (s ∪ s0) ∪ s1 = s ∪ s0 ∪ s1; from specification set-union[refset] ⊦ a ∈ s ∪ s0 ↔ ¬(¬ a ∈ s ∧ ¬ a ∈ s0); (ss)

Proof step 9 from proof lst-in-hp (previous step) (back to tree)

User applied rule apply rewrite lemma

And obtained the following new goals

• Proof step 10:

  ⊦ hR[rs, f, g] ↔ hR(mk(rs, f, g))

• Proof step 11:

  rs0 ∩ rs1 = ∅, r ≠ null, hR[rs1, cf, af], o[ls(r, x)](mk(rs0, cf, af)), ¬ r ∈ rs0, ¬ r ∈ rs1 ⊦

Rule argument

Additional information

Used terms: o[ls(r, x)], rs0, cf, af

Proof step 10 from proof lst-in-hp (previous step) (back to tree)

A spec-lemma

Proof step 11 from proof lst-in-hp (previous step) (back to tree)

User applied rule apply rewrite lemma

And obtained the following new goals

• Proof step 12:

  ⊦ a[hP](mk(rs, f, g)) ↔ hP(mk(rs, f)) ∧ (∀ r. r ∈ rs → g(r) = a)

• Proof step 13:

  rs0 ∩ rs1 = ∅, r ≠ null, hR[rs1, cf, af], ls(r, x)(mk(rs0, cf)), ¬ r ∈ rs0, ¬ r ∈ rs1, ∀ r. r ∈ rs0 → af(r) = o ⊦

Rule argument

Additional information

Used terms: cf, o, ls(r, x), rs0, af

Proof step 12 from proof lst-in-hp (previous step) (back to tree)

A spec-lemma

Proof step 13 from proof lst-in-hp (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 14:

  rs0 ∩ rs1 = ∅, r ≠ null, hR[rs1, cf, af], ls(r, x)(mk(rs0, cf)), ¬ r ∈ rs0, ¬ r ∈ rs1, ∀ r. r ∈ rs0 → af(r) = o ⊦

Rule argument

Additional information

Proof step 14 from proof lst-in-hp (previous step) (back to tree)

User applied rule constructor cut

And obtained the following new goals

• Proof step 15:

  x = a + x0, rs0 ∩ rs1 = ∅, r ≠ null, hR[rs1, cf, af], ls(r, x)(mk(rs0, cf)), ¬ r ∈ rs0, ¬ r ∈ rs1, ∀ r. r ∈ rs0 → af(r) = o ⊦

Rule argument

Additional information

Used simplifier rules: ls-base: ⊦ ls(r, []) = (emp ∧ ⌜r = null⌝ ); list freely generated by [], +;; ⊦ ⌜false⌝ = false; (s) ⊦ (false ∧ hP) = false; (s) and-ass: ⊦ ((hP0 ∧ hP1) ∧ hP2) = (hP0 ∧ hP1 ∧ hP2); from specification heap-sep and-com: ⊦ (hP0 ∧ hP1) = (hP1 ∧ hP0); from specification heap-sep ⊦ ¬ false(h); (s)

Proof step 15 from proof lst-in-hp (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 16:

  rs0 ∩ rs1 = ∅, r ≠ null, ((r => a × r0 * ls(r0, x0)))(mk(rs0, cf)), hR[rs1, cf, af], ¬ r ∈ rs0, ¬ r ∈ rs1, ∀ r. r ∈ rs0 → af(r) = o ⊦

Rule argument

Additional information

Used simplifier rules: ls-rec: ⊦ ls(r, a ' + x) = _∃(λ r0. r => a × r0 * ls(r0, x)); ⊦ (_∃ rP)(h) ↔ (∃ r. rP(r)(h)); (s) a: ⊦ (x + y) + z = x + y + z; from specification list ⊦ a + x = a ' + x; (s)

Proof step 16 from proof lst-in-hp (previous step) (back to tree)

User applied rule apply rewrite lemma

And obtained the following new goals

• Proof step 17:

  ⊦ ((hP0 * hP1))(h) ↔ (∃ h0, h1. h0 ⊥ h1 ∧ h = h0 ∪ h1 ∧ hP0(h0) ∧ hP1(h1))

• Proof step 18:

  rs0 ∩ rs1 = ∅, r ≠ null, hR[rs1, cf, af], ¬ r ∈ rs0, ¬ r ∈ rs1, ∀ r. r ∈ rs0 → af(r) = o, ∃ h0, h1. h0 ⊥ h1 ∧ mk(rs0, cf) = h0 ∪ h1 ∧ ((r => a × r0))(h0) ∧ ls(r0, x0)(h1) ⊦

Rule argument

Additional information

Used terms: mk(rs0, cf), ls(r0, x0), r => a × r0

Proof step 17 from proof lst-in-hp (previous step) (back to tree)

A spec-lemma

Proof step 18 from proof lst-in-hp (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 19:

  mk(rs0, cf) = h0 ∪ h1, rs0 ∩ rs1 = ∅, r ≠ null, ((r => a × r0))(h0), hR[rs1, cf, af], ls(r0, x0)(h1), h0 ⊥ h1, ¬ r ∈ rs0, ¬ r ∈ rs1, ∀ r. r ∈ rs0 → af(r) = o ⊦

Rule argument

Additional information

Proof step 19 from proof lst-in-hp (previous step) (back to tree)

User applied rule apply rewrite lemma

And obtained the following new goals

• Proof step 20:

  ⊦ ((r => o))(h) ↔ h = (∅ ++ r)[r, o] ∧ r ≠ null

• Proof step 21:

  h0 = (∅ ++ r)[r, a × r0], mk(rs0, cf) = h0 ∪ h1, rs0 ∩ rs1 = ∅, r ≠ null, hR[rs1, cf, af], ls(r0, x0)(h1), h0 ⊥ h1, ¬ r ∈ rs0, ¬ r ∈ rs1, ∀ r. r ∈ rs0 → af(r) = o ⊦

Rule argument

Additional information

Used terms: h0, a × r0, r

Proof step 20 from proof lst-in-hp (previous step) (back to tree)

A spec-lemma

Proof step 21 from proof lst-in-hp (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 22:

  mk(rs0, cf) = (∅ ++ r)[r, a × r0] ∪ h1, rs0 ∩ rs1 = ∅, r ≠ null, hR[rs1, cf, af], ls(r0, x0)(h1), ¬ r ∈ rs0, ¬ r ∈ rs1, ¬ r ∈ h1, ∀ r. r ∈ rs0 → af(r) = o ⊦

Rule argument

Additional information

Used simplifier rules: r ≠ null ⊦ (∅ ++ r)[r, o] ⊥ h ↔ ¬ r ∈ h; (s)

Proof step 22 from proof lst-in-hp (previous step) (back to tree)

User applied rule apply rewrite lemma

And obtained the following new goals

• Proof step 23:

  ⊦ h0 = h1 ↔ (∀ r. (r ∈ h0 ↔ r ∈ h1) ∧ (r ∈ h0 → h0[r] = h1[r]))

• Proof step 24:

  rs0 ∩ rs1 = ∅, r ≠ null, hR[rs1, cf, af], ls(r0, x0)(h1), ¬ r ∈ rs0, ¬ r ∈ rs1, ¬ r ∈ h1, ∀ r. r ∈ rs0 → af(r) = o, ∀ r1. (r1 ∈ mk(rs0, cf) ↔ r1 ∈ (∅ ++ r)[r, a × r0] ∪ h1) ∧ (r1 ∈ mk(rs0, cf) → mk(rs0, cf)[r1] = ((∅ ++ r)[r, a × r0] ∪ h1)[r1]) ⊦

Rule argument

Additional information

Used terms: (∅ ++ r)[r, a × r0] ∪ h1, mk(rs0, cf)

Proof step 23 from proof lst-in-hp (previous step) (back to tree)

A spec-lemma

Proof step 24 from proof lst-in-hp (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 25:

  rs0 ∩ rs1 = ∅, r ≠ null, hR[rs1, cf, af], ls(r0, x0)(h1), ¬ r ∈ rs0, ¬ r ∈ rs1, ¬ r ∈ h1, ∀ r. r ∈ rs0 → af(r) = o, ∀ r1. (r1 ∈ rs0 ↔ r1 ∈ (∅ ++ r)[r, a × r0] ∪ h1) ∧ (r1 ∈ rs0 → cf(r1) = ((∅ ++ r)[r, a × r0] ∪ h1)[r1]) ⊦

Rule argument

Additional information

Used simplifier rules: ⊦ r ∈ rs → mk(rs, f)[r] = f(r); (s) ⊦ r ∈ mk(rs, f) ↔ r ∈ rs; (s)

Proof step 25 from proof lst-in-hp (previous step) (back to tree)

User applied rule all left

And obtained the following new goals

• Proof step 26:

  r ∈ rs0 ↔ r ∈ (∅ ++ r)[r, a × r0] ∪ h1, rs0 ∩ rs1 = ∅, r ≠ null, hR[rs1, cf, af], ls(r0, x0)(h1), ¬ r ∈ rs0, ¬ r ∈ rs1, ¬ r ∈ h1, r ∈ rs0 → cf(r) = ((∅ ++ r)[r, a × r0] ∪ h1)[r], ∀ r. r ∈ rs0 → af(r) = o ⊦

Rule argument

Additional information

Used terms: r

Proof step 26 from proof lst-in-hp (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 27:

  rs0 ∩ rs1 = ∅, r ≠ null, hR[rs1, cf, af], ls(r0, x0)(h1), ¬ r ∈ rs0, ¬ r ∈ rs1, ¬ r ∈ h1, ¬ r ∈ (∅ ++ r)[r, a × r0] ∪ h1, ∀ r. r ∈ rs0 → af(r) = o ⊦

Rule argument

Additional information

Proof step 27 from proof lst-in-hp (previous step) (back to tree)

User applied rule apply rewrite lemma

And obtained the following new goals

• Proof step 28:

  ⊦ h0 ⊥ h1 → (r ∈ h0 ∪ h1 ↔ r ∈ h0 ∨ r ∈ h1)

Rule argument

Additional information

Used simplifier rules: r ≠ null ⊦ (∅ ++ r)[r, o] ⊥ h ↔ ¬ r ∈ h; (s) ⊦ r ∈ h[r0, o] ↔ r ∈ h; (s) ⊦ ¬ r ∈ ∅; (s) r0 ≠ null, ¬ r0 ∈ h ⊦ r ∈ h ++ r0 ↔ r = r0 ∨ r ∈ h; (s) Used terms: h1, (∅ ++ r)[r, a × r0], r

Proof step 28 from proof lst-in-hp (previous step) (back to tree)

A spec-lemma