Structure Omega_AutomataTheory


Source File Identifier index Theory binding index

signature Omega_AutomataTheory =
sig
  type thm = Thm.thm

  (*  Theorems  *)
    val AUTOMATON_TEMP_CLOSURE : thm
    val BEFORE_AS_CO_BUECHI : thm
    val BOOLEAN_CLOSURE_F : thm
    val BOOLEAN_CLOSURE_FG : thm
    val BOOLEAN_CLOSURE_G : thm
    val BOOLEAN_CLOSURE_GF : thm
    val BOREL_HIERARCHY_F : thm
    val BOREL_HIERARCHY_FG : thm
    val BOREL_HIERARCHY_G : thm
    val BUECHI_PERIODIC_MODEL : thm
    val BUECHI_PERIODIC_REDUCTION_THM : thm
    val BUECHI_PROP_REDUCTION : thm
    val BUECHI_TRANSLATION : thm
    val CO_BUECHI_BEFORE_CLOSURE : thm
    val CO_BUECHI_CONJ_CLOSURE : thm
    val CO_BUECHI_DISJ_CLOSURE : thm
    val CO_BUECHI_NEXT_CLOSURE : thm
    val CO_BUECHI_SBEFORE_CLOSURE : thm
    val CO_BUECHI_SUNTIL_CLOSURE : thm
    val CO_BUECHI_SWHEN_CLOSURE : thm
    val CO_BUECHI_UNTIL_CLOSURE : thm
    val CO_BUECHI_WHEN_CLOSURE : thm
    val DET_OMEGA_EXISTS_FORALL_THEOREM : thm
    val ELGOT1_THM : thm
    val ELGOT2_THM : thm
    val ELGOT_LEMMA : thm
    val EQUALITY_THM : thm
    val EXISTS_FORALL_THM : thm
    val FORALL_EXISTS_THM : thm
    val LESS_THM : thm
    val NEG_DET_AUTOMATA : thm
    val NEXT_AS_CO_BUECHI : thm
    val OMEGA_CONJ_CLOSURE : thm
    val OMEGA_DISJ_CLOSURE : thm
    val SBEFORE_AS_CO_BUECHI : thm
    val SUNTIL_AS_CO_BUECHI : thm
    val SWHEN_AS_CO_BUECHI : thm
    val TEMP_OPS_DEFS_TO_OMEGA : thm
    val UNTIL_AS_CO_BUECHI : thm
    val WHEN_AS_CO_BUECHI : thm

  val Omega_Automata_grammars : type_grammar.grammar * term_grammar.grammar
(*
   [Past_Temporal_Logic] Parent theory of "Omega_Automata"

   [AUTOMATON_TEMP_CLOSURE]  Theorem

      |- ((∃q1.
             Phi_I1 q1 ∧ Phi_R1 q1 ∧
             ∃q2. Phi_I2 q2 ∧ Phi_R2 (q2,q1) ∧ Phi_F (q1,q2)) ⇔
          ∃q1 q2.
            (Phi_I1 q1 ∧ Phi_I2 q2) ∧ (Phi_R1 q1 ∧ Phi_R2 (q2,q1)) ∧
            Phi_F (q1,q2)) ∧
         (Phi (NEXT phi) ⇔
          ∃q0 q1.
            T ∧ (∀t. (q0 t ⇔ phi t) ∧ (q1 t ⇔ q0 (t + 1))) ∧ Phi q1) ∧
         (Phi (PNEXT phi) ⇔ ∃q. q 0 ∧ (∀t. q (t + 1) ⇔ phi t) ∧ Phi q) ∧
         (Phi (PSNEXT phi) ⇔ ∃q. ¬q 0 ∧ (∀t. q (t + 1) ⇔ phi t) ∧ Phi q) ∧
         (Phi (PNEXT (PALWAYS a)) ⇔
          ∃q. q 0 ∧ (∀t. q (t + 1) ⇔ a t ∧ q t) ∧ Phi q) ∧
         (Phi (PSNEXT (PEVENTUAL a)) ⇔
          ∃q. ¬q 0 ∧ (∀t. q (t + 1) ⇔ a t ∨ q t) ∧ Phi q) ∧
         (Phi (PSNEXT (a PSUNTIL b)) ⇔
          ∃q. ¬q 0 ∧ (∀t. q (t + 1) ⇔ b t ∨ a t ∧ q t) ∧ Phi q) ∧
         (Phi (PSNEXT (a PSWHEN b)) ⇔
          ∃q. ¬q 0 ∧ (∀t. q (t + 1) ⇔ a t ∧ b t ∨ ¬b t ∧ q t) ∧ Phi q) ∧
         (Phi (PSNEXT (a PSBEFORE b)) ⇔
          ∃q. ¬q 0 ∧ (∀t. q (t + 1) ⇔ ¬b t ∧ (a t ∨ q t)) ∧ Phi q) ∧
         (Phi (PNEXT (a PUNTIL b)) ⇔
          ∃q. q 0 ∧ (∀t. q (t + 1) ⇔ b t ∨ a t ∧ q t) ∧ Phi q) ∧
         (Phi (PNEXT (a PWHEN b)) ⇔
          ∃q. q 0 ∧ (∀t. q (t + 1) ⇔ a t ∧ b t ∨ ¬b t ∧ q t) ∧ Phi q) ∧
         (Phi (PNEXT (a PBEFORE b)) ⇔
          ∃q. q 0 ∧ (∀t. q (t + 1) ⇔ ¬b t ∧ (a t ∨ q t)) ∧ Phi q)

   [BEFORE_AS_CO_BUECHI]  Theorem

      |- (a BEFORE b) t0 ⇔
         ∃q.
           ¬q t0 ∧
           (∀t.
              ¬q (t + t0) ∧ ¬a (t + t0) ∧ ¬b (t + t0) ∧ ¬q (t + (1 + t0)) ∨
              ¬q (t + t0) ∧ a (t + t0) ∧ ¬b (t + t0) ∧ q (t + (1 + t0)) ∨
              q (t + t0) ∧ q (t + (1 + t0))) ∧
           ∃t1. ∀t2. ¬q (t1 + (t2 + t0)) ∨ q (t1 + (t2 + t0))

   [BOOLEAN_CLOSURE_F]  Theorem

      |- (¬(∃t. a (t + t0)) ⇔ ∀t. ¬a (t + t0)) ∧
         ((∃t. a (t + t0)) ∨ (∃t. b (t + t0)) ⇔
          ∃t. a (t + t0) ∨ b (t + t0)) ∧
         ((∃t. a (t + t0)) ∧ (∃t. b (t + t0)) ⇔
          ∃p q.
            (¬p t0 ∧ ¬q t0) ∧
            (∀t.
               (p (t + (t0 + 1)) ⇔ p (t + t0) ∨ a (t + t0)) ∧
               (q (t + (t0 + 1)) ⇔ q (t + t0) ∨ b (t + t0))) ∧
            ∃t. p (t + t0) ∧ q (t + t0))

   [BOOLEAN_CLOSURE_FG]  Theorem

      |- (¬(∃t1. ∀t2. a (t1 + (t2 + t0))) ⇔
          ∀t1. ∃t2. ¬a (t1 + (t2 + t0))) ∧
         ((∃t1. ∀t2. a (t1 + (t2 + t0))) ∧ (∃t1. ∀t2. b (t1 + (t2 + t0))) ⇔
          ∃t1. ∀t2. a (t1 + (t2 + t0)) ∧ b (t1 + (t2 + t0))) ∧
         ((∃t1. ∀t2. a (t1 + (t2 + t0))) ∨ (∃t1. ∀t2. b (t1 + (t2 + t0))) ⇔
          ∃q.
            ¬q t0 ∧
            (∀t.
               q (t + (t0 + 1)) ⇔
               if q (t + t0) then b (t + t0) else ¬a (t + t0)) ∧
            ∃t1. ∀t2. ¬q (t1 + (t2 + t0)) ∨ b (t1 + (t2 + t0)))

   [BOOLEAN_CLOSURE_G]  Theorem

      |- (¬(∀t. a (t + t0)) ⇔ ∃t. ¬a (t + t0)) ∧
         ((∀t. a (t + t0)) ∧ (∀t. b (t + t0)) ⇔
          ∀t. a (t + t0) ∧ b (t + t0)) ∧
         ((∀t. a (t + t0)) ∨ (∀t. b (t + t0)) ⇔
          ∃p q.
            (¬p t0 ∧ ¬q t0) ∧
            (∀t.
               (p (t + (t0 + 1)) ⇔ p (t + t0) ∨ ¬a (t + t0)) ∧
               (q (t + (t0 + 1)) ⇔ q (t + t0) ∨ ¬b (t + t0))) ∧
            ∀t. ¬p (t + t0) ∨ ¬q (t + t0))

   [BOOLEAN_CLOSURE_GF]  Theorem

      |- (¬(∀t1. ∃t2. a (t1 + (t2 + t0))) ⇔
          ∃t1. ∀t2. ¬a (t1 + (t2 + t0))) ∧
         ((∀t1. ∃t2. a (t1 + (t2 + t0))) ∨ (∀t1. ∃t2. b (t1 + (t2 + t0))) ⇔
          ∀t1. ∃t2. a (t1 + (t2 + t0)) ∨ b (t1 + (t2 + t0))) ∧
         ((∀t1. ∃t2. a (t1 + (t2 + t0))) ∧ (∀t1. ∃t2. b (t1 + (t2 + t0))) ⇔
          ∃q.
            ¬q t0 ∧
            (∀t.
               q (t + (t0 + 1)) ⇔
               if q (t + t0) then ¬b (t + t0) else a (t + t0)) ∧
            ∀t1. ∃t2. q (t1 + (t2 + t0)) ∧ b (t1 + (t2 + t0)))

   [BOREL_HIERARCHY_F]  Theorem

      |- ((∃t. a (t + t0)) ⇔
          ∃q.
            ¬q t0 ∧ (∀t. q (SUC (t + t0)) ⇔ q (t + t0) ∨ a (t + t0)) ∧
            ∃t1. ∀t2. q (t1 + (t2 + t0))) ∧
         ((∃t. a (t + t0)) ⇔
          ∃q.
            ¬q t0 ∧ (∀t. q (SUC (t + t0)) ⇔ q (t + t0) ∨ a (t + t0)) ∧
            ∀t1. ∃t2. q (t1 + (t2 + t0)))

   [BOREL_HIERARCHY_FG]  Theorem

      |- ((∃t1. ∀t2. a (t1 + (t2 + t0))) ⇔
          ∃q.
            ¬q t0 ∧ (∀t. q (t + t0) ⇒ a (t + t0) ∧ q (SUC (t + t0))) ∧
            ∃t. q (t + t0)) ∧
         ((∃t1. ∀t2. a (t1 + (t2 + t0))) ⇔
          ∃p q.
            (¬p t0 ∧ ¬q t0) ∧
            (∀t.
               (p (t + t0) ⇒ p (SUC (t + t0))) ∧
               (p (SUC (t + t0)) ⇒ p (t + t0) ∨ ¬q (t + t0)) ∧
               (q (SUC (t + t0)) ⇔
                p (t + t0) ∧ ¬q (t + t0) ∧ ¬a (t + t0) ∨
                p (t + t0) ∧ q (t + t0))) ∧
            ∀t1. ∃t2. p (t1 + (t2 + t0)) ∧ ¬q (t1 + (t2 + t0)))

   [BOREL_HIERARCHY_G]  Theorem

      |- ((∀t. a (t + t0)) ⇔
          ∃q.
            q t0 ∧ (∀t. q (t + t0) ∧ a (t + t0) ∧ q (SUC (t + t0))) ∧
            ∃t. q (t + t0)) ∧
         ((∀t. a (t + t0)) ⇔
          ∃q.
            q t0 ∧ (∀t. q (SUC (t + t0)) ⇔ q (t + t0) ∧ a (t + t0)) ∧
            ∃t1. ∀t2. q (t1 + (t2 + t0))) ∧
         ((∀t. a (t + t0)) ⇔
          ∃q.
            q t0 ∧ (∀t. q (SUC (t + t0)) ⇔ q (t + t0) ∧ a (t + t0)) ∧
            ∀t1. ∃t2. q (t1 + (t2 + t0)))

   [BUECHI_PERIODIC_MODEL]  Theorem

      |- (∀s. ∃x0 l. 0 < l ∧ (s x0 = s (x0 + l))) ⇒
         ((∃i q.
             InitState (q 0) ∧ (∀t. TransRel (i t,q t,q (t + 1))) ∧
             ∀t1. ∃t2. Accept (q (t1 + t2))) ⇔
          ∃x0 l j p.
            0 < l ∧ (∀t2. j (x0 + t2) = j (x0 + t2 MOD l)) ∧
            (∀t2. p (x0 + t2) = p (x0 + t2 MOD l)) ∧ InitState (p 0) ∧
            (∀t. TransRel (j t,p t,p (t + 1))) ∧
            ∀t1. ∃t2. Accept (p (t1 + t2)))

   [BUECHI_PERIODIC_REDUCTION_THM]  Theorem

      |- (∀s. ∃x0 l. 0 < l ∧ (s x0 = s (x0 + l))) ⇒
         ((∃i q.
             InitState (q 0) ∧ (∀t. TransRel (i t,q t,q (t + 1))) ∧
             ∀t1. ∃t2. Accept (q (t1 + t2))) ⇔
          ∃x0 l j p.
            0 < l ∧ (∀t2. j (x0 + t2) = j (x0 + t2 MOD l)) ∧
            (∀t2. p (x0 + t2) = p (x0 + t2 MOD l)) ∧ InitState (p 0) ∧
            (∀t. t < x0 + l ⇒ TransRel (j t,p t,p (t + 1))) ∧
            ∃t. t < l ∧ Accept (p (x0 + t)))

   [BUECHI_PROP_REDUCTION]  Theorem

      |- (∀s. ∃x0 l. 0 < l ∧ (s x0 = s (x0 + l))) ⇒
         ((∃i q.
             InitState (q 0) ∧ (∀t. TransRel (i t,q t,q (t + 1))) ∧
             ∀t1. ∃t2. Accept (q (t1 + t2))) ⇔
          ∃x0 l j p.
            0 < l ∧ InitState (p 0) ∧
            (∀t. t < x0 + l ⇒ TransRel (j t,p t,p (t + 1))) ∧
            (∃t. t < l ∧ Accept (p (x0 + t))) ∧ (p x0 = p (x0 + l)))

   [BUECHI_TRANSLATION]  Theorem

      |- (Phi (NEXT phi) ⇔
          ∃q0 q1.
            T ∧ (∀t. (q0 t ⇔ phi t) ∧ (q1 t ⇔ q0 (t + 1))) ∧ Phi q1) ∧
         (Phi (ALWAYS a) ⇔
          ∃q.
            T ∧ (∀t. q t ⇔ a t ∧ q (t + 1)) ∧
            (∀t1. ∃t2. a (t1 + t2) ⇒ q (t1 + t2)) ∧ Phi q) ∧
         (Phi (EVENTUAL a) ⇔
          ∃q.
            T ∧ (∀t. q t ⇔ a t ∨ q (t + 1)) ∧
            (∀t1. ∃t2. q (t1 + t2) ⇒ a (t1 + t2)) ∧ Phi q) ∧
         (Phi (a SUNTIL b) ⇔
          ∃q.
            T ∧ (∀t. q t ⇔ b t ∨ a t ∧ q (t + 1)) ∧
            (∀t1. ∃t2. q (t1 + t2) ⇒ ¬a (t1 + t2) ∨ b (t1 + t2)) ∧ Phi q) ∧
         (Phi (a UNTIL b) ⇔
          ∃q.
            T ∧ (∀t. q t ⇔ b t ∨ a t ∧ q (t + 1)) ∧
            (∀t1. ∃t2. ¬q (t1 + t2) ⇒ ¬a (t1 + t2) ∨ b (t1 + t2)) ∧
            Phi q) ∧
         (Phi (a SWHEN b) ⇔
          ∃q.
            T ∧ (∀t. q t ⇔ if b t then a t else q (t + 1)) ∧
            (∀t1. ∃t2. q (t1 + t2) ⇒ b (t1 + t2)) ∧ Phi q) ∧
         (Phi (a WHEN b) ⇔
          ∃q.
            T ∧ (∀t. q t ⇔ if b t then a t else q (t + 1)) ∧
            (∀t1. ∃t2. q (t1 + t2) ∨ b (t1 + t2)) ∧ Phi q) ∧
         (Phi (a SBEFORE b) ⇔
          ∃q.
            T ∧ (∀t. q t ⇔ ¬b t ∧ (a t ∨ q (t + 1))) ∧
            (∀t1. ∃t2. q (t1 + t2) ⇒ a (t1 + t2) ∨ b (t1 + t2)) ∧ Phi q) ∧
         (Phi (a BEFORE b) ⇔
          ∃q.
            T ∧ (∀t. q t ⇔ ¬b t ∧ (a t ∨ q (t + 1))) ∧
            (∀t1. ∃t2. ¬q (t1 + t2) ⇒ a (t1 + t2) ∨ b (t1 + t2)) ∧ Phi q)

   [CO_BUECHI_BEFORE_CLOSURE]  Theorem

      |- ((λt0.
             ∃q.
               Phi_I (q t0) ∧ (∀t. Phi_R (i (t + t0),q (t + t0))) ∧
               ∃t1.
                 ∀t2. Psi (i (t1 + (t2 + t0)),q (t1 + (t2 + t0)))) BEFORE
          phi) t0 ⇔
         ∃p1 p2 q.
           (¬p1 t0 ∧ ¬p2 t0 ∧ (q t0 = c) ∨ p1 t0 ∧ ¬p2 t0 ∧ Phi_I (q t0)) ∧
           (∀t.
              ¬p1 (t + t0) ∧ ¬p2 (t + t0) ∧ (q (t + t0) = c) ∧
              ¬phi (t + t0) ∧ ¬p1 (t + (t0 + 1)) ∧ ¬p2 (t + (t0 + 1)) ∧
              (q (t + (t0 + 1)) = c) ∨
              ¬p1 (t + t0) ∧ ¬p2 (t + t0) ∧ (q (t + t0) = c) ∧
              ¬phi (t + t0) ∧ p1 (t + (t0 + 1)) ∧ ¬p2 (t + (t0 + 1)) ∧
              Phi_I (q (t + (t0 + 1))) ∨
              p1 (t + t0) ∧ ¬p2 (t + t0) ∧ ¬phi (t + t0) ∧
              Phi_I (q (t + t0)) ∧ Phi_R (i (t + t0),q (t + t0)) ∧
              p1 (t + (t0 + 1)) ∧ p2 (t + (t0 + 1)) ∨
              p1 (t + t0) ∧ p2 (t + t0) ∧ Phi_R (i (t + t0),q (t + t0)) ∧
              p1 (t + (t0 + 1)) ∧ p2 (t + (t0 + 1))) ∧
           ∃t1.
             ∀t2.
               ¬p1 (t1 + (t2 + t0)) ∨
               Psi (i (t1 + (t2 + t0)),q (t1 + (t2 + t0)))

   [CO_BUECHI_CONJ_CLOSURE]  Theorem

      |- (∃q1.
            Phi_I1 (q1 t0) ∧ (∀t. Phi_R1 (i (t + t0),q1 (t + t0))) ∧
            ∃t1. ∀t2. Psi1 (i (t1 + (t2 + t0)),q1 (t1 + (t2 + t0)))) ∧
         (∃q2.
            Phi_I2 (q2 t0) ∧ (∀t. Phi_R2 (i (t + t0),q2 (t + t0))) ∧
            ∃t1. ∀t2. Psi2 (i (t1 + (t2 + t0)),q2 (t1 + (t2 + t0)))) ⇔
         ∃q1 q2.
           (Phi_I1 (q1 t0) ∧ Phi_I2 (q2 t0)) ∧
           (∀t.
              Phi_R1 (i (t + t0),q1 (t + t0)) ∧
              Phi_R2 (i (t + t0),q2 (t + t0))) ∧
           ∃t1.
             ∀t2.
               Psi1 (i (t1 + (t2 + t0)),q1 (t1 + (t2 + t0))) ∧
               Psi2 (i (t1 + (t2 + t0)),q2 (t1 + (t2 + t0)))

   [CO_BUECHI_DISJ_CLOSURE]  Theorem

      |- (∃q1.
            Phi_I1 (q1 t0) ∧ (∀t. Phi_R1 (i (t + t0),q1 (t + t0))) ∧
            ∃t1. ∀t2. Psi1 (i (t1 + (t2 + t0)),q1 (t1 + (t2 + t0)))) ∨
         (∃q2.
            Phi_I2 (q2 t0) ∧ (∀t. Phi_R2 (i (t + t0),q2 (t + t0))) ∧
            ∃t1. ∀t2. Psi2 (i (t1 + (t2 + t0)),q2 (t1 + (t2 + t0)))) ⇔
         ∃p q1 q2.
           (¬p t0 ∧ Phi_I1 (q1 t0) ∨ p t0 ∧ Phi_I2 (q2 t0)) ∧
           (∀t.
              ¬p (t + t0) ∧ Phi_R1 (i (t + t0),q1 (t + t0)) ∧
              ¬p (t + (t0 + 1)) ∨
              p (t + t0) ∧ Phi_R2 (i (t + t0),q2 (t + t0)) ∧
              p (t + (t0 + 1))) ∧
           ∃t1.
             ∀t2.
               ¬p (t + t0) ∧
               Psi1 (i (t1 + (t2 + t0)),q1 (t1 + (t2 + t0))) ∨
               p (t + t0) ∧ Psi2 (i (t1 + (t2 + t0)),q2 (t1 + (t2 + t0)))

   [CO_BUECHI_NEXT_CLOSURE]  Theorem

      |- NEXT
           (λt0.
              ∃q.
                Phi_I (q t0) ∧ (∀t. Phi_R (i (t + t0),q (t + t0))) ∧
                ∃t1. ∀t2. Psi (i (t1 + (t2 + t0)),q (t1 + (t2 + t0)))) t0 ⇔
         ∃p q.
           ((p t0 ⇔ F) ∧ (q t0 = c)) ∧
           (∀t.
              ¬p (t + t0) ∧ (q (t + t0) = c) ∧ p (t + (t0 + 1)) ∧
              Phi_I (q (t + (t0 + 1))) ∨
              p (t + t0) ∧ Phi_R (i (t + t0),q (t + t0)) ∧
              p (t + (t0 + 1))) ∧
           ∃t1. ∀t2. Psi (i (t1 + (t2 + t0)),q (t1 + (t2 + t0)))

   [CO_BUECHI_SBEFORE_CLOSURE]  Theorem

      |- ((λt0.
             ∃q.
               Phi_I (q t0) ∧ (∀t. Phi_R (i (t + t0),q (t + t0))) ∧
               ∃t1.
                 ∀t2. Psi (i (t1 + (t2 + t0)),q (t1 + (t2 + t0)))) SBEFORE
          phi) t0 ⇔
         ∃p1 p2 q.
           (¬p1 t0 ∧ ¬p2 t0 ∧ (q t0 = c) ∨ p1 t0 ∧ ¬p2 t0 ∧ Phi_I (q t0)) ∧
           (∀t.
              ¬p1 (t + t0) ∧ ¬p2 (t + t0) ∧ (q (t + t0) = c) ∧
              ¬phi (t + t0) ∧ ¬p1 (t + (t0 + 1)) ∧ ¬p2 (t + (t0 + 1)) ∧
              (q (t + (t0 + 1)) = c) ∨
              ¬p1 (t + t0) ∧ ¬p2 (t + t0) ∧ (q (t + t0) = c) ∧
              ¬phi (t + t0) ∧ p1 (t + (t0 + 1)) ∧ ¬p2 (t + (t0 + 1)) ∧
              Phi_I (q (t + (t0 + 1))) ∨
              p1 (t + t0) ∧ ¬p2 (t + t0) ∧ ¬phi (t + t0) ∧
              Phi_I (q (t + t0)) ∧ Phi_R (i (t + t0),q (t + t0)) ∧
              p1 (t + (t0 + 1)) ∧ p2 (t + (t0 + 1)) ∨
              p1 (t + t0) ∧ p2 (t + t0) ∧ Phi_R (i (t + t0),q (t + t0)) ∧
              p1 (t + (t0 + 1)) ∧ p2 (t + (t0 + 1))) ∧
           ∃t1.
             ∀t2.
               p1 (t1 + (t2 + t0)) ∧
               Psi (i (t1 + (t2 + t0)),q (t1 + (t2 + t0)))

   [CO_BUECHI_SUNTIL_CLOSURE]  Theorem

      |- (phi SUNTIL
          (λt0.
             ∃q.
               Phi_I (q t0) ∧ (∀t. Phi_R (i (t + t0),q (t + t0))) ∧
               ∃t1. ∀t2. Psi (i (t1 + (t2 + t0)),q (t1 + (t2 + t0))))) t0 ⇔
         ∃p q.
           (if p t0 then Phi_I (q t0) else (q t0 = c)) ∧
           (∀t.
              ¬p (t + t0) ∧ (q (t + t0) = c) ∧ phi (t + t0) ∧
              ¬p (t + (t0 + 1)) ∧ (q (t + (t0 + 1)) = c) ∨
              ¬p (t + t0) ∧ (q (t + t0) = c) ∧ phi (t + t0) ∧
              p (t + (t0 + 1)) ∧ Phi_I (q (t + (t0 + 1))) ∨
              p (t + t0) ∧ Phi_R (i (t + t0),q (t + t0)) ∧
              p (t + (t0 + 1))) ∧
           ∃t1.
             ∀t2.
               p (t1 + (t2 + t0)) ∧
               Psi (i (t1 + (t2 + t0)),q (t1 + (t2 + t0)))

   [CO_BUECHI_SWHEN_CLOSURE]  Theorem

      |- ((λt0.
             ∃q.
               Phi_I (q t0) ∧ (∀t. Phi_R (i (t + t0),q (t + t0))) ∧
               ∃t1. ∀t2. Psi (i (t1 + (t2 + t0)),q (t1 + (t2 + t0)))) SWHEN
          phi) t0 ⇔
         ∃p1 p2 q.
           (¬p1 t0 ∧ ¬p2 t0 ∧ (q t0 = c) ∨ p1 t0 ∧ ¬p2 t0 ∧ Phi_I (q t0)) ∧
           (∀t.
              ¬p1 (t + t0) ∧ ¬p2 (t + t0) ∧ (q (t + t0) = c) ∧
              ¬phi (t + t0) ∧ ¬p1 (t + (t0 + 1)) ∧ ¬p2 (t + (t0 + 1)) ∧
              (q (t + (t0 + 1)) = c) ∨
              ¬p1 (t + t0) ∧ ¬p2 (t + t0) ∧ (q (t + t0) = c) ∧
              ¬phi (t + t0) ∧ p1 (t + (t0 + 1)) ∧ ¬p2 (t + (t0 + 1)) ∧
              Phi_I (q (t + (t0 + 1))) ∨
              p1 (t + t0) ∧ ¬p2 (t + t0) ∧ phi (t + t0) ∧
              Phi_I (q (t + t0)) ∧ Phi_R (i (t + t0),q (t + t0)) ∧
              p1 (t + (t0 + 1)) ∧ p2 (t + (t0 + 1)) ∨
              p1 (t + t0) ∧ p2 (t + t0) ∧ Phi_R (i (t + t0),q (t + t0)) ∧
              p1 (t + (t0 + 1)) ∧ p2 (t + (t0 + 1))) ∧
           ∃t1.
             ∀t2.
               p1 (t1 + (t2 + t0)) ∧
               Psi (i (t1 + (t2 + t0)),q (t1 + (t2 + t0)))

   [CO_BUECHI_UNTIL_CLOSURE]  Theorem

      |- (phi UNTIL
          (λt0.
             ∃q.
               Phi_I (q t0) ∧ (∀t. Phi_R (i (t + t0),q (t + t0))) ∧
               ∃t1. ∀t2. Psi (i (t1 + (t2 + t0)),q (t1 + (t2 + t0))))) t0 ⇔
         ∃p q.
           (if p t0 then Phi_I (q t0) else (q t0 = c)) ∧
           (∀t.
              ¬p (t + t0) ∧ (q (t + t0) = c) ∧ phi (t + t0) ∧
              ¬p (t + (t0 + 1)) ∧ (q (t + (t0 + 1)) = c) ∨
              ¬p (t + t0) ∧ (q (t + t0) = c) ∧ phi (t + t0) ∧
              p (t + (t0 + 1)) ∧ Phi_I (q (t + (t0 + 1))) ∨
              p (t + t0) ∧ Phi_R (i (t + t0),q (t + t0)) ∧
              p (t + (t0 + 1))) ∧
           ∃t1.
             ∀t2.
               ¬p (t1 + (t2 + t0)) ∨
               Psi (i (t1 + (t2 + t0)),q (t1 + (t2 + t0)))

   [CO_BUECHI_WHEN_CLOSURE]  Theorem

      |- ((λt0.
             ∃q.
               Phi_I (q t0) ∧ (∀t. Phi_R (i (t + t0),q (t + t0))) ∧
               ∃t1. ∀t2. Psi (i (t1 + (t2 + t0)),q (t1 + (t2 + t0)))) WHEN
          phi) t0 ⇔
         ∃p1 p2 q.
           (¬p1 t0 ∧ ¬p2 t0 ∧ (q t0 = c) ∨ p1 t0 ∧ ¬p2 t0 ∧ Phi_I (q t0)) ∧
           (∀t.
              ¬p1 (t + t0) ∧ ¬p2 (t + t0) ∧ (q (t + t0) = c) ∧
              ¬phi (t + t0) ∧ ¬p1 (t + (t0 + 1)) ∧ ¬p2 (t + (t0 + 1)) ∧
              (q (t + (t0 + 1)) = c) ∨
              ¬p1 (t + t0) ∧ ¬p2 (t + t0) ∧ (q (t + t0) = c) ∧
              ¬phi (t + t0) ∧ p1 (t + (t0 + 1)) ∧ ¬p2 (t + (t0 + 1)) ∧
              Phi_I (q (t + (t0 + 1))) ∨
              p1 (t + t0) ∧ ¬p2 (t + t0) ∧ phi (t + t0) ∧
              Phi_I (q (t + t0)) ∧ Phi_R (i (t + t0),q (t + t0)) ∧
              p1 (t + (t0 + 1)) ∧ p2 (t + (t0 + 1)) ∨
              p1 (t + t0) ∧ p2 (t + t0) ∧ Phi_R (i (t + t0),q (t + t0)) ∧
              p1 (t + (t0 + 1)) ∧ p2 (t + (t0 + 1))) ∧
           ∃t1.
             ∀t2.
               ¬p1 (t1 + (t2 + t0)) ∨
               Psi (i (t1 + (t2 + t0)),q (t1 + (t2 + t0)))

   [DET_OMEGA_EXISTS_FORALL_THEOREM]  Theorem

      |- (∃q.
            (q t0 = InitVal) ∧
            (∀t. q (t + (t0 + 1)) = TransRel (i (t + t0),q (t + t0))) ∧
            Accept (i,(λt. q (t + t0)))) ⇔
         ∀q.
           (q t0 = InitVal) ∧
           (∀t. q (t + (t0 + 1)) = TransRel (i (t + t0),q (t + t0))) ⇒
           Accept (i,(λt. q (t + t0)))

   [ELGOT1_THM]  Theorem

      |- ∀PHI. (∃x. ∀p. PHI p x) ⇔ ∃q. ∀p x. ∃z. (q x ⇒ PHI p x) ∧ q z

   [ELGOT2_THM]  Theorem

      |- ∀PHI. (∀x. ∃p. PHI p x) ⇔ ∀q. ∃p x. ∀z. q z ⇒ PHI p x ∧ q x

   [ELGOT_LEMMA]  Theorem

      |- ∀PHI. (∃x. ∀p. PHI p x) ⇔ ∃q. (∀x. q x ⇒ ∀p. PHI p x) ∧ ∃z. q z

   [EQUALITY_THM]  Theorem

      |- ∀x y. (x = y) ⇔ ∀P. P x ⇔ P y

   [EXISTS_FORALL_THM]  Theorem

      |- ∀P. (∃t1. ∀t2. P (t1 + t2)) ⇔ ∃t1. ∀t2. t1 < t2 ⇒ P t2

   [FORALL_EXISTS_THM]  Theorem

      |- ∀P. (∀t1. ∃t2. P (t1 + t2)) ⇔ ∀t1. ∃t2. t1 < t2 ∧ P t2

   [LESS_THM]  Theorem

      |- ∀x y. x < y ⇔ ∃P. P x ∧ ¬P y ∧ ∀z. P (SUC z) ⇒ P z

   [NEG_DET_AUTOMATA]  Theorem

      |- ¬(∃q.
             (q t0 = InitVal) ∧
             (∀t. q (t + (t0 + 1)) = TransRel (i (t + t0),q (t + t0))) ∧
             Accept (i,(λt. q (t + t0)))) ⇔
         ∃q.
           (q t0 = InitVal) ∧
           (∀t. q (t + (t0 + 1)) = TransRel (i (t + t0),q (t + t0))) ∧
           ¬Accept (i,(λt. q (t + t0)))

   [NEXT_AS_CO_BUECHI]  Theorem

      |- NEXT a t0 ⇔
         ∃p q.
           (¬p t0 ∧ ¬q t0) ∧
           (∀t.
              ¬p (t + t0) ∧ ¬q (t + t0) ∧ p (t + (1 + t0)) ∧
              ¬q (t + (1 + t0)) ∨
              p (t + t0) ∧ ¬q (t + t0) ∧ a (t + t0) ∧ p (t + (1 + t0)) ∧
              q (t + (1 + t0)) ∨
              p (t + t0) ∧ q (t + t0) ∧ p (t + (1 + t0)) ∧
              q (t + (1 + t0))) ∧ ∃t1. ∀t2. q (t1 + (t2 + t0))

   [OMEGA_CONJ_CLOSURE]  Theorem

      |- (∃q1.
            Phi_I1 (q1 t0) ∧ (∀t. Phi_R1 (i (t + t0),q1 (t + t0))) ∧
            Psi1 (i,q1)) ∧
         (∃q2.
            Phi_I2 (q2 t0) ∧ (∀t. Phi_R2 (i (t + t0),q2 (t + t0))) ∧
            Psi2 (i,q2)) ⇔
         ∃q1 q2.
           (Phi_I1 (q1 t0) ∧ Phi_I2 (q2 t0)) ∧
           (∀t.
              Phi_R1 (i (t + t0),q1 (t + t0)) ∧
              Phi_R2 (i (t + t0),q2 (t + t0))) ∧ Psi1 (i,q1) ∧ Psi2 (i,q2)

   [OMEGA_DISJ_CLOSURE]  Theorem

      |- (∃q1.
            Phi_I1 (q1 t0) ∧ (∀t. Phi_R1 (i (t + t0),q1 (t + t0))) ∧
            Psi1 (i,q1)) ∨
         (∃q2.
            Phi_I2 (q2 t0) ∧ (∀t. Phi_R2 (i (t + t0),q2 (t + t0))) ∧
            Psi2 (i,q2)) ⇔
         ∃p q1 q2.
           (¬p t0 ∧ Phi_I1 (q1 t0) ∨ p t0 ∧ Phi_I2 (q2 t0)) ∧
           (∀t.
              ¬p (t + t0) ∧ Phi_R1 (i (t + t0),q1 (t + t0)) ∧
              ¬p (t + (t0 + 1)) ∨
              p (t + t0) ∧ Phi_R2 (i (t + t0),q2 (t + t0)) ∧
              p (t + (t0 + 1))) ∧
           (¬p t0 ∧ Psi1 (i,q1) ∨ p t0 ∧ Psi2 (i,q2))

   [SBEFORE_AS_CO_BUECHI]  Theorem

      |- (a SBEFORE b) t0 ⇔
         ∃q.
           ¬q t0 ∧
           (∀t.
              ¬q (t + t0) ∧ ¬a (t + t0) ∧ ¬b (t + t0) ∧ ¬q (t + (1 + t0)) ∨
              ¬q (t + t0) ∧ a (t + t0) ∧ ¬b (t + t0) ∧ q (t + (1 + t0)) ∨
              q (t + t0) ∧ q (t + (1 + t0))) ∧ ∃t1. ∀t2. q (t1 + (t2 + t0))

   [SUNTIL_AS_CO_BUECHI]  Theorem

      |- (a SUNTIL b) t0 ⇔
         ∃q.
           ¬q t0 ∧
           (∀t.
              ¬q (t + t0) ∧ a (t + t0) ∧ ¬b (t + t0) ∧ ¬q (t + (1 + t0)) ∨
              ¬q (t + t0) ∧ b (t + t0) ∧ q (t + (1 + t0)) ∨
              q (t + t0) ∧ q (t + (1 + t0))) ∧ ∃t1. ∀t2. q (t1 + (t2 + t0))

   [SWHEN_AS_CO_BUECHI]  Theorem

      |- (a SWHEN b) t0 ⇔
         ∃q.
           ¬q t0 ∧
           (∀t.
              ¬q (t + t0) ∧ ¬b (t + t0) ∧ ¬q (t + (1 + t0)) ∨
              ¬q (t + t0) ∧ a (t + t0) ∧ b (t + t0) ∧ q (t + (1 + t0)) ∨
              q (t + t0) ∧ q (t + (1 + t0))) ∧ ∃t1. ∀t2. q (t1 + (t2 + t0))

   [TEMP_OPS_DEFS_TO_OMEGA]  Theorem

      |- ((l = NEXT a) ⇔ T ∧ (∀t. l t ⇔ a (SUC t)) ∧ T) ∧
         ((l = ALWAYS a) ⇔
          T ∧ (∀t. l t ⇔ a t ∧ l (SUC t)) ∧
          ∀t1. ∃t2. a (t1 + t2) ⇒ l (t1 + t2)) ∧
         ((l = EVENTUAL a) ⇔
          T ∧ (∀t. l t ⇔ a t ∨ l (SUC t)) ∧
          ∀t1. ∃t2. l (t1 + t2) ⇒ a (t1 + t2)) ∧
         ((l = a SUNTIL b) ⇔
          T ∧ (∀t. l t ⇔ ¬b t ⇒ a t ∧ l (SUC t)) ∧
          ∀t1. ∃t2. l (t1 + t2) ⇒ ¬a (t1 + t2) ∨ b (t1 + t2)) ∧
         ((l = a SWHEN b) ⇔
          T ∧ (∀t. l t ⇔ if b t then a t else l (SUC t)) ∧
          ∀t1. ∃t2. l (t1 + t2) ⇒ b (t1 + t2)) ∧
         ((l = a SBEFORE b) ⇔
          T ∧ (∀t. l t ⇔ ¬b t ∧ (a t ∨ l (SUC t))) ∧
          ∀t1. ∃t2. l (t1 + t2) ⇒ a (t1 + t2) ∨ b (t1 + t2)) ∧
         ((l = a UNTIL b) ⇔
          T ∧ (∀t. l t ⇔ ¬b t ⇒ a t ∧ l (SUC t)) ∧
          ∀t1. ∃t2. ¬l (t1 + t2) ⇒ ¬a (t1 + t2) ∨ b (t1 + t2)) ∧
         ((l = a WHEN b) ⇔
          T ∧ (∀t. l t ⇔ if b t then a t else l (SUC t)) ∧
          ∀t1. ∃t2. l (t1 + t2) ∨ b (t1 + t2)) ∧
         ((l = a BEFORE b) ⇔
          T ∧ (∀t. l t ⇔ ¬b t ∧ (a t ∨ l (SUC t))) ∧
          ∀t1. ∃t2. ¬l (t1 + t2) ⇒ a (t1 + t2) ∨ b (t1 + t2)) ∧
         ((l = PNEXT a) ⇔ (l 0 ⇔ T) ∧ (∀t. l (SUC t) ⇔ a t) ∧ T) ∧
         ((l = PSNEXT a) ⇔ (l 0 ⇔ F) ∧ (∀t. l (SUC t) ⇔ a t) ∧ T) ∧
         ((l = PNEXT (PALWAYS a)) ⇔
          (l 0 ⇔ T) ∧ (∀t. l (SUC t) ⇔ a t ∧ l t) ∧ T) ∧
         ((l = PSNEXT (PEVENTUAL a)) ⇔
          (l 0 ⇔ F) ∧ (∀t. l (SUC t) ⇔ a t ∨ l t) ∧ T) ∧
         ((l = PSNEXT (a PSUNTIL b)) ⇔
          (l 0 ⇔ F) ∧ (∀t. l (SUC t) ⇔ b t ∨ a t ∧ l t) ∧ T) ∧
         ((l = PSNEXT (a PSWHEN b)) ⇔
          (l 0 ⇔ F) ∧ (∀t. l (SUC t) ⇔ a t ∧ b t ∨ ¬b t ∧ l t) ∧ T) ∧
         ((l = PSNEXT (a PSBEFORE b)) ⇔
          (l 0 ⇔ F) ∧ (∀t. l (SUC t) ⇔ ¬b t ∧ (a t ∨ l t)) ∧ T) ∧
         ((l = PNEXT (a PUNTIL b)) ⇔
          (l 0 ⇔ T) ∧ (∀t. l (SUC t) ⇔ b t ∨ a t ∧ l t) ∧ T) ∧
         ((l = PNEXT (a PWHEN b)) ⇔
          (l 0 ⇔ T) ∧ (∀t. l (SUC t) ⇔ a t ∧ b t ∨ ¬b t ∧ l t) ∧ T) ∧
         ((l = PNEXT (a PBEFORE b)) ⇔
          (l 0 ⇔ T) ∧ (∀t. l (SUC t) ⇔ ¬b t ∧ (a t ∨ l t)) ∧ T)

   [UNTIL_AS_CO_BUECHI]  Theorem

      |- (a UNTIL b) t0 ⇔
         ∃q.
           ¬q t0 ∧
           (∀t.
              ¬q (t + t0) ∧ a (t + t0) ∧ ¬b (t + t0) ∧ ¬q (t + (1 + t0)) ∨
              ¬q (t + t0) ∧ b (t + t0) ∧ q (t + (1 + t0)) ∨
              q (t + t0) ∧ q (t + (1 + t0))) ∧
           ∃t1. ∀t2. ¬q (t1 + (t2 + t0)) ∨ q (t1 + (t2 + t0))

   [WHEN_AS_CO_BUECHI]  Theorem

      |- (a WHEN b) t0 ⇔
         ∃q.
           ¬q t0 ∧
           (∀t.
              ¬q (t + t0) ∧ ¬b (t + t0) ∧ ¬q (t + (1 + t0)) ∨
              ¬q (t + t0) ∧ a (t + t0) ∧ b (t + t0) ∧ q (t + (1 + t0)) ∨
              q (t + t0) ∧ q (t + (1 + t0))) ∧
           ∃t1. ∀t2. ¬q (t1 + (t2 + t0)) ∨ q (t1 + (t2 + t0))


*)
end


Source File Identifier index Theory binding index

HOL 4, Kananaskis-11