src/HOL/UNITY/Priority.thy

new examples by Sidi Ehmety

(*  Title:      HOL/UNITY/Priority
    ID:         $Id$
    Author:     Sidi O Ehmety, Cambridge University Computer Laboratory
    Copyright   2001  University of Cambridge

The priority system

From Charpentier and Chandy,
Examples of Program Composition Illustrating the Use of Universal Properties
   In J. Rolim (editor), Parallel and Distributed Processing,
   Spriner LNCS 1586 (1999), pages 1215-1227.
*)

Priority = PriorityAux + Comp + SubstAx +

types state = "(vertex*vertex)set"
types command = "vertex=>(state*state)set"
  
consts
  (* the initial state *)
  init :: "(vertex*vertex)set"  

constdefs
  (* from the definitions given in section 4.4 *)
  (* i has highest priority in r *)
  highest :: "[vertex, (vertex*vertex)set]=>bool"
  "highest i r == A i r = {}"
  
  (* i has lowest priority in r *)
  lowest :: "[vertex, (vertex*vertex)set]=>bool"
  "lowest i r == R i r = {}"

  act :: command
  "act i == {(s, s'). s'=reverse i s & highest i s}"

  (* All components start with the same initial state *)
  Component :: "vertex=>state program"
  "Component i == mk_program({init}, {act i}, UNIV)"

  (* Abbreviations *)
  Highest :: "vertex=>state set"
  "Highest i == {s. highest i s}"

  Lowest :: "vertex=>state set"
  "Lowest i == {s. lowest i s}"

  Acyclic :: "state set"
  "Acyclic == {s. acyclic s}"

  (* Every above set has a maximal vertex: two equivalent defs. *)

  Maximal :: "state set"
  "Maximal == INT i. {s. ~highest i s-->(EX j:above i  s. highest j s)}"

  Maximal' :: "state set"
  "Maximal' == INT i. Highest i Un (UN j. {s. j:above i s} Int Highest j)"

  
  Safety :: "state set"
  "Safety == INT i. {s. highest i s --> (ALL j:neighbors i s. ~highest j s)}"


  (* Composition of a finite set of component;
     the vertex 'UNIV' is finite by assumption *)
  
  system :: "state program"
  "system == JN i. Component i"
end