SSL Common.thy Interaktion und
PortierbarkeitIsabelle

(*  Title:      HOL/UNITY/Simple/Common.thy
    Author:     Lawrence C Paulson, Cambridge University Computer Laboratory
    Copyright   1998  University of Cambridge

Common Meeting Time example from Misra (1994)

The state is identified with the one variable in existence.

From Misra, "A Logic for Concurrent Programming" (1994), sections 5.1 and 13.1.
*)

theory Common
imports "../UNITY_Main"
begin

consts
  ftime :: "nat=>nat"
  gtime :: "nat=>nat"

axiomatization where
  fmono: "m \ n ==> ftime m \ ftime n" and
  gmono: "m \ n ==> gtime m \ gtime n" and

  fasc:  "m \ ftime n" and
  gasc:  "m \ gtime n"

definition common :: "nat set" where
    "common == {n. ftime n = n & gtime n = n}"

definition maxfg :: "nat => nat set" where
    "maxfg m == {t. t \ max (ftime m) (gtime m)}"

(*Misra's property CMT4: t exceeds no common meeting time*)
lemma common_stable:
     "[| \m. F \ {m} Co (maxfg m); n \ common |]
      ==> F \<in> Stable (atMost n)"
apply (drule_tac M = "{t. t \ n}" in Elimination_sing)
apply (simp add: atMost_def Stable_def common_def maxfg_def le_max_iff_disj)
apply (erule Constrains_weaken_R)
apply (blast intro: order_eq_refl le_trans dest: fmono gmono)
done

lemma common_safety:
     "[| Init F \ atMost n;
         \<forall>m. F \<in> {m} Co (maxfg m); n \<in> common |]
      ==> F \<in> Always (atMost n)"
by (simp add: AlwaysI common_stable)

(*** Some programs that implement the safety property above ***)

lemma "SKIP \ {m} co (maxfg m)"
by (simp add: constrains_def maxfg_def le_max_iff_disj fasc)

(*This one is  t := ftime t || t := gtime t*)
lemma "mk_total_program
         (UNIV, {range(%t.(t,ftime t)), range(%t.(t,gtime t))}, UNIV)
       \<in> {m} co (maxfg m)"
apply (simp add: mk_total_program_def)
apply (simp add: constrains_def maxfg_def le_max_iff_disj fasc)
done

(*This one is  t := max (ftime t) (gtime t)*)
lemma "mk_total_program (UNIV, {range(%t.(t, max (ftime t) (gtime t)))}, UNIV)
       \<in> {m} co (maxfg m)"
apply (simp add: mk_total_program_def)
apply (simp add: constrains_def maxfg_def gasc max.absorb2)
done

(*This one is  t := t+1 if t <max (ftime t) (gtime t) *)
lemma  "mk_total_program
          (UNIV, { {(t, Suc t) | t. t < max (ftime t) (gtime t)} }, UNIV)
       \<in> {m} co (maxfg m)"
apply (simp add: mk_total_program_def)
apply (simp add: constrains_def maxfg_def gasc max.absorb2)
done

(*It remans to prove that they satisfy CMT3': t does not decrease,
  and that CMT3' implies that t stops changing once common(t) holds.*)

(*** Progress under weak fairness ***)

lemma leadsTo_common_lemma:
  assumes "\m. F \ {m} Co (maxfg m)"
    and "\m \ lessThan n. F \ {m} LeadsTo (greaterThan m)"
    and "n \ common"
  shows "F \ (atMost n) LeadsTo common"
proof (rule LeadsTo_weaken_R)
  show "F \ {..n} LeadsTo {..n} \ id -` {n..} \ common"
  proof (induct rule: GreaterThan_bounded_induct [of n _ _ id])
    case 1
    from assms have "\m\{.. {..n} \ {m} LeadsTo {..n} \ {m<..} \ common"
      by (blast dest: PSP_Stable2 intro: common_stable LeadsTo_weaken_R)
    then show ?case by simp
  qed
next
  from \<open>n \<in> common\<close>
  show "{..n} \ id -` {n..} \ common \ common"
    by (simp add: atMost_Int_atLeast)
qed

(*The "\<forall>m \<in> -common" form echoes CMT6.*)
lemma leadsTo_common:
     "[| \m. F \ {m} Co (maxfg m);
         \<forall>m \<in> -common. F \<in> {m} LeadsTo (greaterThan m);
         n \<in> common |]
      ==> F \<in> (atMost (LEAST n. n \<in> common)) LeadsTo common"
apply (rule leadsTo_common_lemma)
apply (simp_all (no_asm_simp))
apply (erule_tac [2] LeastI)
apply (blast dest!: not_less_Least)
done

end

quality98%

¤ Diese beiden folgenden Angebotsgruppen bietet das Unternehmen0.13Angebot Wie Sie bei der Firma Beratungs- und Dienstleistungen beauftragen können ¤

*Eine klare Vorstellung vom Zielzustand

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.

SSL Common.thy Interaktion und PortierbarkeitIsabelle

¤ Diese beiden folgenden Angebotsgruppen bietet das Unternehmen0.13Angebot Wie Sie bei der Firma Beratungs- und Dienstleistungen beauftragen können ¤

Haftungshinweis

Bemerkung:

SSL Common.thy Interaktion und
PortierbarkeitIsabelle