Theory Confluence

theory Confluence imports
  Main
begin

section ‹Confluence›

definition semiconfluentp :: "('a ⇒ 'a ⇒ bool) ⇒ bool" where
  "semiconfluentp r ⟷ r¯¯ OO r⇧^*⇧^* ≤ r⇧^*⇧^* OO r¯¯⇧^*⇧^*"

definition confluentp :: "('a ⇒ 'a ⇒ bool) ⇒ bool" where
  "confluentp r ⟷ r¯¯⇧^*⇧^* OO r⇧^*⇧^* ≤ r⇧^*⇧^* OO r¯¯⇧^*⇧^*"

definition strong_confluentp :: "('a ⇒ 'a ⇒ bool) ⇒ bool" where
  "strong_confluentp r ⟷ r¯¯ OO r ≤ r⇧^*⇧^* OO (r¯¯)⇧⁼⇧⁼"

lemma semiconfluentpI [intro?]:
  "semiconfluentp r" if "⋀x y z. ⟦ r x y; r⇧^*⇧^* x z ⟧ ⟹ ∃u. r⇧^*⇧^* y u ∧ r⇧^*⇧^* z u"
  using that unfolding semiconfluentp_def rtranclp_conversep by blast

lemma semiconfluentpD: "∃u. r⇧^*⇧^* y u ∧ r⇧^*⇧^* z u" if "semiconfluentp r" "r x y" "r⇧^*⇧^* x z"
  using that unfolding semiconfluentp_def rtranclp_conversep by blast

lemma confluentpI:
  "confluentp r" if "⋀x y z. ⟦ r⇧^*⇧^* x y; r⇧^*⇧^* x z ⟧ ⟹ ∃u. r⇧^*⇧^* y u ∧ r⇧^*⇧^* z u"
  using that unfolding confluentp_def rtranclp_conversep by blast

lemma confluentpD: "∃u. r⇧^*⇧^* y u ∧ r⇧^*⇧^* z u" if "confluentp r" "r⇧^*⇧^* x y" "r⇧^*⇧^* x z"
  using that unfolding confluentp_def rtranclp_conversep by blast

lemma strong_confluentpI [intro?]:
  "strong_confluentp r" if "⋀x y z. ⟦ r x y; r x z ⟧ ⟹ ∃u. r⇧^*⇧^* y u ∧ r⇧⁼⇧⁼ z u"
  using that unfolding strong_confluentp_def by blast

lemma strong_confluentpD: "∃u. r⇧^*⇧^* y u ∧ r⇧⁼⇧⁼ z u" if "strong_confluentp r" "r x y" "r x z"
  using that unfolding strong_confluentp_def by blast

lemma semiconfluentp_imp_confluentp: "confluentp r" if r: "semiconfluentp r"
proof(rule confluentpI)
  show "∃u. r⇧^*⇧^* y u ∧ r⇧^*⇧^* z u" if "r⇧^*⇧^* x y" "r⇧^*⇧^* x z" for x y z
    using that(2,1)
    by(induction arbitrary: y rule: converse_rtranclp_induct)
      (blast intro: rtranclp_trans dest:  r[THEN semiconfluentpD])+
qed

lemma confluentp_imp_semiconfluentp: "semiconfluentp r" if "confluentp r"
  using that by(auto intro!: semiconfluentpI dest: confluentpD[OF that])

lemma confluentp_eq_semiconfluentp: "confluentp r ⟷ semiconfluentp r"
  by(blast intro: semiconfluentp_imp_confluentp confluentp_imp_semiconfluentp)

lemma confluentp_conv_strong_confluentp_rtranclp:
  "confluentp r ⟷ strong_confluentp (r⇧^*⇧^*)"
  by(auto simp add: confluentp_def strong_confluentp_def rtranclp_conversep)

lemma strong_confluentp_into_semiconfluentp:
  "semiconfluentp r" if r: "strong_confluentp r"
proof
  show "∃u. r⇧^*⇧^* y u ∧ r⇧^*⇧^* z u" if "r x y" "r⇧^*⇧^* x z" for x y z
    using that(2,1)
    apply(induction arbitrary: y rule: converse_rtranclp_induct)
    subgoal by blast
    subgoal for a b c
      by (drule (1) strong_confluentpD[OF r, of a c])(auto 10 0 intro: rtranclp_trans)
    done
qed

lemma strong_confluentp_imp_confluentp: "confluentp r" if "strong_confluentp r"
  unfolding confluentp_eq_semiconfluentp using that by(rule strong_confluentp_into_semiconfluentp)

lemma semiconfluentp_equivclp: "equivclp r = r⇧^*⇧^* OO r¯¯⇧^*⇧^*" if r: "semiconfluentp r"
proof(rule antisym[rotated] r_OO_conversep_into_equivclp predicate2I)+
  show "(r⇧^*⇧^* OO r¯¯⇧^*⇧^*) x y" if "equivclp r x y" for x y using that unfolding equivclp_def rtranclp_conversep
    by(induction rule: converse_rtranclp_induct)
      (blast elim!: symclpE intro: converse_rtranclp_into_rtranclp rtranclp_trans dest: semiconfluentpD[OF r])+
qed

end