[Imprint][Data Privacy Statement][E-Mail]

Back to main index. View the specification. View theorem base summary, View theorem base listing, the used properties by spec, the dependency list, the symbol table,

Specification abs
enrich
   DMSQ-proofs, 
   DQ-proofs
with
   functions 
       content : reflist × heap → list;
       ren : DMSQAction → DQAction;
       abspc : DMSQGState × DMSQLState × DMSQPC → DQPC;
   
   predicates 
       abs : DMSQState × DQState;
       absls : DMSQGState × DMSQLState × DMSQPC × DQLState;
       DMSQastep : DMSQState × DQAction × DMSQState;
       DMSQinit : DMSQState;
       DQinit : DQState;
   
   variables 
       gs : DMSQGState;
       ags : DQGState;
       cs : DMSQState;
       lsf : Tid → DMSQLState;
       alsf : Tid → DQLState;
       pcf : Tid → DMSQPC;
       apcf : Tid → DQPC;
       ls : DMSQLState;
       als : DQLState;
       pc : DMSQPC;
       apc : DQPC;
       aa : DQAction;
       ca : DMSQAction;
       q : list;
       tid : Tid;
       vs : heap;
       ps : heap;
       val : elem;
       optval : OptElem;
       nd : Node;
       success : bool;
       rvref : rvRef;
       r : Ref;
       rl : reflist;
   
   
   axioms 
      DMSQinit-def: 
        DMSQinit(mkstate(gs, lsf, pcf))
      ↔   (∃ r, val. 
               r ≠ null ∧ gs.ps = ∅[r, mk(val, Some(dummytid), null)] ∧ gs.phead = r ∧ gs.vhead = r ∧ gs.vtail = r ∧ gs.orl = r ' ∧ gs.qrl = []
             ∧ gs.vs = gs.ps)
        ∧ gs.vrvHp = ∅ ∧ gs.prvHp = ∅ ∧ gs.vretRefs = (λ tid. null) ∧ gs.pretRefs = (λ tid. null) ∧ gs.owns = (λ r. None) ∧ pcf = (λ tid. idle)
        ∧ (∀ tid. lsf(tid).tid = tid);
      comment: a predicate identical to the initial state of the automaton DMSQ (except lsf(tid).tid = tid was implicit);
      
      DQinit-def: DQinit(mkstate(ags, alsf, apcf)) ↔ ags.queue = [] ∧ apcf = (λ tid. idle) ∧ (∀ tid. alsf(tid).tid = tid);
      comment: a predicate identical to the initial state of the automaton DQ (except lsf(tid).tid = tid was implicit);
      
      DMSQastep-def: DMSQastep(cs, aa, cs0) ↔ (∃ ca. ren(ca) = aa ∧ DMSQstep(cs, ca, cs0));
      used for: ls, s;
      
      ren-chooseE: ren(chooseE1(r, nd, success)) = τ;
      used for: s, ls;
      
      ren-chooseD: ren(chooseD2(rvref, optval0)) = τ;
      used for: s, ls;
      
      ren-invENQ: ren(invENQ(tid, val)) = InvEnq(tid, val);
      used for: s, ls;
      
      ren-invDEQ: ren(invDEQ(tid)) = InvDeq(tid);
      used for: s, ls;
      
      ren-retDEQ: ren(retDEQ(tid, optval)) = RetDeq(tid, optval);
      used for: s, ls;
      
      ren-retENQ: ren(retENQ(tid)) = RetEnq(tid);
      used for: s, ls;
      
      ren-callRUN: ren(callRUN(tid)) = callRun(tid);
      used for: s, ls;
      
      ren-doDeq: ren(doDeq(tid)) = DoDeq(tid);
      used for: s, ls;
      
      ren-doDeqEmpty: ren(doDeqEmpty(tid)) = DoDeqEmpty(tid);
      used for: s, ls;
      
      ren-doEnq: ren(doEnq(tid)) = DoEnq(tid);
      used for: s, ls;
      
      ren-tau: ren(τ) = τ;
      used for: s, ls;
      
      ren-CRASH: ren(globalCRASH) = globalCrash;
      used for: s, ls;
      
      ren-FLUSHHEAD: ren(globalFLUSHHEAD) = τ;
      used for: s, ls;
      
      ren-FLUSHVAL: ren(globalFLUSHVAL(r)) = τ;
      used for: s, ls;
      
      ren-checkEmp: ren(checkEmp(tid)) = CheckEmp(tid);
      used for: s, ls;
      
      abs-def: 
        abs(mkstate(gs, lsf, pcf), mkstate(mkgs(q), alsf, apcf))
      ↔ q = content(gs.qrl, gs.ps) ∧ (∀ tid. absls(gs, lsf(tid), pcf(tid), alsf(tid)) ∧ abspc(gs, lsf(tid), pcf(tid)) = apcf(tid));
      
      absls-def: 
        absls(gs, ls, pc, als)
      ↔   ls.tid = als.tid
        ∧ (    pc = E1 ∨ pc = E2 ∨ pc = E3 ∨ pc = E4 ∧ ¬ ls.success ∨ pc = E5 ∨ pc = E6 ∨ pc = E7 ∨ pc = E8 ∨ pc = E9
             ∨ pc = E10 ∧ (ls.success → ls.lst = gs.vtail ∧ gs.ps[ls.lst].next = null) ∨ pc = E11 ∧ ls.lst = gs.vtail ∧ gs.ps[ls.lst].next = null
             ∨ pc = E13 ∨ pc = E14 ∨ pc = E15 ∨ pc = E16
           → ls.value = als.ival)
        ∧ ((pc = D10 ∨ pc = D11 ∨ pc = D12 ∨ pc = D13 ∨ pc = D14) ∧ ls.nxt = null → als.obsEmpty)
        ∧ (pc = D20 ∧ ls.success ∧ gs.ps[ls.nxt].deqID ≠ None ∨ pc = D21 ∧ gs.ps[ls.nxt].deqID ≠ None ∨ pc = D22 → als.oval = ls.optval)
        ∧ (pc = D15 ∨ pc = D23 ∨ pc = D24 ∨ pc = D6 ∧ ls.success ∨ pc = D34 → als.oval = gs.vrvHp[gs.vretRefs(ls.tid)]);
      
      abspc-def: 
        abspc(gs, ls, pc)
      = (pc = idle
        ⊃ idle
        ;(pc = ready
         ⊃ ready
         ;(pc = crashed
          ⊃ crashed
          ;(  pc = E1 ∨ pc = E2 ∨ pc = E3 ∨ pc = E4 ∧ ¬ ls.success ∨ pc = E5 ∨ pc = E6 ∨ pc = E7 ∨ pc = E8 ∨ pc = E9
            ∨ pc = E10 ∧ (ls.success → ls.lst = gs.vtail ∧ gs.ps[ls.lst].next = null) ∨ pc = E11 ∧ ls.lst = gs.vtail ∧ gs.ps[ls.lst].next = null
            ∨ pc = E13 ∨ pc = E14 ∨ pc = E15 ∨ pc = E16
           ⊃ invEnq
           ;(pc = E10 ∨ pc = E11 ∨ pc = E12 ∨ pc = E4 ∨ pc = E13 ∨ pc = E17
            ⊃ resEnq
            ;(  pc = D1 ∨ pc = D2 ∨ pc = D3 ∨ pc = D4 ∨ pc = D5 ∨ pc = D6 ∧ ¬ ls.success ∨ pc = D7 ∨ pc = D8 ∨ pc = D9 ∨ pc = D10 ∨ pc = D11
              ∨ pc = D12 ∨ pc = D13 ∨ pc = D14 ∨ pc = D16 ∨ pc = D17 ∨ pc = D18 ∨ pc = D19 ∨ pc = D20 ∧ (ls.success → gs.ps[ls.nxt].deqID = None)
              ∨ pc = D21 ∧ gs.ps[ls.nxt].deqID = None ∨ pc = D25 ∨ pc = D26 ∨ pc = D27 ∨ pc = D28 ∨ pc = D29 ∨ pc = D30 ∨ pc = D31 ∨ pc = D32
              ∨ pc = D33
             ⊃ invDeq
             ;resDeq
             )
            )
           )
          )
         )
        );
      used for: ls;
      
      content-base: content([], ps) = [];
      used for: s, ls;
      
      content-rec: content(r ' + rl, ps) = ps[r].val + content(rl, ps);
      used for: s, ls;
   
   
end enrich