Specifying Adaptive Program Behaviour Using Temporal Logic
Transcrição
Specifying Adaptive Program Behaviour Using Temporal Logic
Specifying Adaptive Program Behaviour Using Temporal Logic Based on the article “Using Temporal Logic to Specify Adaptive Program Semantics” by Ji Zhang and Betty H.C. Cheng Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik an der Universität Paderborn Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik Outline 1 Introduction Motivation Linear Temporal Logic 2 Model Checking of Adaptive Programs Program Properties Adapt-Operator Extended LTL Adaptation Techniques 3 Discussion Summary Conclusion 2/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik Why Adaptive Software? Software must react to changing conditions e.g. Embedded software of an amphibious vehicle going into the water Software must cope with hardware malfunction e.g. Loss of a harddisk in a RAID system Software needs to change its behaviour according to these changes 3/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik Program Representation A program is list of statements that is ready to be executed Suitable example: a Petri-Net Example A road where cars go from “On-Ramp” to “Off-Ramp” On-Ramp Off-Ramp Ready transitions On-Ramp → Off-Ramp 4/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik Program Representation A program is list of statements that is ready to be executed Suitable example: a Petri-Net Example A road where cars go from “On-Ramp” to “Off-Ramp” On-Ramp Off-Ramp Ready transitions On-Ramp → Off-Ramp 4/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik Program Representation A program is list of statements that is ready to be executed Suitable example: a Petri-Net Example It is replaced by a detour around a construction site Detour On-Ramp Off-Ramp Ready transitions On-Ramp → Detour 4/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik Program Representation A program is list of statements that is ready to be executed Suitable example: a Petri-Net Example It is replaced by a detour around a construction site Detour On-Ramp Off-Ramp Ready transitions On-Ramp → Detour Detour → Off-Ramp 4/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik Program Representation A program is list of statements that is ready to be executed Suitable example: a Petri-Net Example It is replaced by a detour around a construction site Detour On-Ramp Off-Ramp Ready transitions On-Ramp → Detour 4/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik Program Representation A program is list of statements that is ready to be executed Suitable example: a Petri-Net Example Finally, the original road is restored Detour On-Ramp Off-Ramp Ready transitions On-Ramp → Off-Ramp 4/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik Program Representation A program is list of statements that is ready to be executed Suitable example: a Petri-Net Example Finally, the original road is restored Detour On-Ramp Off-Ramp Ready transitions 4/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik Why Model Checking? Software is expected to work correct In some systems even small errors may result in huge costs or people being killed e.g. First flight of Ariane 5, which exploded because of a small software bug Hence software is checked against its specification 5/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik Software Specification Program: How software does something By a sequence of instructions Specification: What software is expected to do Described by a Product Requirements Document By Temporal Logic (e.g. Linear Temporal Logic) Does a program fulfil its specification? 6/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik Linear Temporal Logic (LTL) ϕ X ϕ (next) ϕ (always) ^ ϕ (eventually) ϕ U ψ (until) 7/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik Properties for Adaptive Programs Specification of a program can be described as a set of properties that a program must fulfil. Properties... which ensure that nothing bad happens ⇒ Safety Properties which ensure that something happens at all ⇒ Liveness Properties that always hold, regardless which program is active ⇒ Global Invariants 8/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik Global Invariants Some properties must always hold, regardless of the current program state Example “Cars do not disappear, except at Off-Ramp” ∀c ∈ Cars : (c is not at Off-Ramp → X ∃R ∈ Road : c is at R) 9/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik Global Invariants Some properties must always hold, regardless of the current program state Example “Cars do not disappear, except at Off-Ramp” ∀c ∈ Cars : (c is not at Off-Ramp → X ∃R ∈ Road : c is at R) Note: LTL does not support quantification (∀, ∃). Hence, these must be expanded: c1 is not at Off-Ramp → X (c1 is at R1 ) ∨ (c1 is at R2 ) ∨ . . . ∧ c2 is not at Off-Ramp → X (c2 is at R1 ) ∨ (c2 is at R2 ) ∨ . . . ∧ . . . 9/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik Point-Safety Properties “Nothing bad may happen” ¬η where η is a point formula Example “No car gets off the road” ¬ ∃c ∈ Cars, ∀R ∈ Road : c is not at R | {z } η 10/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik Point-Liveness Properties “If something happens, the program must react” (α → ^ β) where α and β are point formulae Example “Every car at the On-Ramp reaches the Off-Ramp” ∀c ∈ Cars : (c is at On-Ramp → ^ c is at Off-Ramp) | {z } | {z } α β 11/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik The Adapt-Operator We separate time into phases: Source program phase: Before adaptation event (SSpec holds) Target program phase: After adaptation event (TSpec holds) Ω = (ΩS , ΩT ) holds during the transition ΩS is a point-property that holds at the last state of the source program phase ΩT is a point-property that holds at the first state of the target program phase INV holds at both phases global invariants (INV ) source program (SSpec ) Ω target program (TSpec ) ΩS ΩT 12/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik Formal Definition (A-LTL) Check existence of such phases by a new operator: Ω (ΩS ,ΩT ) SSpec * TSpec Formal: SSpec * TSpec holds in the infinite sequence (s0 , s1 , . . . ) iff there exists a state si such that SSpec holds in (s0 , s1 , . . . , si−1 , si , si , si , . . . ) TSpec holds in (si+1 , si+2 , si+3 , . . . ) ΩS holds at si ΩT holds at si+1 global invariants (INV ) source program (SSpec ) Ω target program (TSpec ) ΩS ΩT 13/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik Correctness for Point-Safety and Point-Liveness (INV * INV ) ⇒ INV ? Preservation of Point-Safety Properties Let SSpec = TSpec = ¬η, i.e. ( ¬η) * ( ¬η) Then ¬η holds as a global invariant. Preservation of Point-Liveness Properties Let SSpec = TSpec = (α → ^ β), i.e. (α → ^ β) * (α → ^ β) Then (α → ^ β) holds as a global invariant. 14/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik Adaptation Techniques (Overview) How to Change the Active Program How to make the transition between two programs? One-Point Adaptation Guided Adaptation Overlap Adaptation 15/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik One-Point Adaptation Ω SSpec ∧ ^ AReq * TSpec global invariants (INV ) source program (SSpec ) Ω target program (TSpec ) AReq Example INV = ∀c ∈ Cars : (c at On-Ramp ⇒ ^ c at Off-Ramp) (All cars eventually reach Off-Ramp) SSpec = ∀c ∈ Cars : ¬(c not at On-Ramp ∧ c not at Off-Ramp) (All cars are on the road) AReq = Start of construction TSpec = ∀c ∈ Cars : ¬(c not at On-Ramp ∧ c not at Off-Ramp ∧ c not at Detour) (All cars are on the road or detour) 16/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik One-Point Adaptation (Example) On-Ramp Source Program Off-Ramp Formula global invariants (INV ) source program (SSpec ) Ω target program (TSpec ) INV Ω SSpec ∧ ^ AReq * TSpec Example AReq INV All cars reach Off-Ramp SSpec All cars on road AReq Start of construction TSpec All cars on road or detour 17/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik One-Point Adaptation (Example) On-Ramp Source Program Off-Ramp Formula global invariants (INV ) source program (SSpec ) Ω target program (TSpec ) INV Ω SSpec ∧ ^ AReq * TSpec Example AReq INV All cars reach Off-Ramp SSpec All cars on road AReq Start of construction TSpec All cars on road or detour 17/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik One-Point Adaptation (Example) On-Ramp Source Program Target Program Off-Ramp Detour On-Ramp Off-Ramp Formula global invariants (INV ) source program (SSpec ) Ω target program (TSpec ) INV Ω SSpec ∧ ^ AReq * TSpec Example AReq INV All cars reach Off-Ramp SSpec All cars on road AReq Start of construction TSpec All cars on road or detour 17/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik One-Point Adaptation (Example) On-Ramp Source Program Off-Ramp m n adapt Detour Target Program On-Ramp m n Off-Ramp Formula global invariants (INV ) source program (SSpec ) Ω target program (TSpec ) INV Ω SSpec ∧ ^ AReq * TSpec Example AReq INV All cars reach Off-Ramp SSpec All cars on road AReq Start of construction TSpec All cars on road or detour 17/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik One-Point Adaptation (Example) On-Ramp Source Program Off-Ramp m n adapt Detour Target Program On-Ramp m n Off-Ramp Formula global invariants (INV ) source program (SSpec ) Ω target program (TSpec ) INV Ω SSpec ∧ ^ AReq * TSpec Example AReq INV All cars reach Off-Ramp SSpec All cars on road AReq Start of construction TSpec All cars on road or detour 17/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik One-Point Adaptation (Example) Target Program Detour On-Ramp Off-Ramp Formula global invariants (INV ) source program (SSpec ) Ω target program (TSpec ) INV Ω SSpec ∧ ^ AReq * TSpec Example AReq INV All cars reach Off-Ramp SSpec All cars on road AReq Start of construction TSpec All cars on road or detour 17/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik One-Point Adaptation (Example) Target Program Detour On-Ramp Off-Ramp Formula global invariants (INV ) source program (SSpec ) Ω target program (TSpec ) INV Ω SSpec ∧ ^ AReq * TSpec Example AReq INV All cars reach Off-Ramp SSpec All cars on road AReq Start of construction TSpec All cars on road or detour 17/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik One-Point Adaptation (Example) Target Program Detour On-Ramp Off-Ramp Formula global invariants (INV ) source program (SSpec ) Ω target program (TSpec ) INV Ω SSpec ∧ ^ AReq * TSpec Example AReq INV All cars reach Off-Ramp SSpec All cars on road AReq Start of construction TSpec All cars on road or detour 17/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik Guided Adaptation Ω1 SSpec ∧ ^ AReq * RCond Ω2 * TSpec global invariants (INV ) Ω2 target program (TSpec ) source program (SSpec ) Ω1 restriction (R Cond ) AReq safe state Example INV = All cars eventually reach Off-Ramp SSpec = All cars are on the road or detour AReq = Construction finished RCond = No car enters the detour TSpec = All cars are on the road 18/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik Guided Adaptation (Example) Source Program Detour On-Ramp Off-Ramp Formula global invariants (INV ) Ω2 target program (TSpec ) source program (SSpec ) Ω1 restriction (R INV Ω2 Ω1 SSpec ∧ ^ AReq * RCond * TSpec Cond ) Example AReq safe state INV All cars reach Off-Ramp SSpec All cars on road or detour AReq Construction finished RCond No cars enter the detour TSpec All cars on road 19/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik Guided Adaptation (Example) Source Program Detour On-Ramp On-Ramp Off-Ramp Target Program Off-Ramp Formula global invariants (INV ) Ω2 target program (TSpec ) source program (SSpec ) Ω1 restriction (R INV Ω2 Ω1 SSpec ∧ ^ AReq * RCond * TSpec Cond ) Example AReq safe state INV All cars reach Off-Ramp SSpec All cars on road or detour AReq Construction finished RCond No cars enter the detour TSpec All cars on road 19/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik Guided Adaptation (Example) Source Program Detour On-Ramp On-Ramp Off-Ramp Target Program Off-Ramp Formula global invariants (INV ) Ω2 target program (TSpec ) source program (SSpec ) Ω1 restriction (R INV Ω2 Ω1 SSpec ∧ ^ AReq * RCond * TSpec Cond ) Example AReq safe state INV All cars reach Off-Ramp SSpec All cars on road or detour AReq Construction finished RCond No cars enter the detour TSpec All cars on road 19/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik Guided Adaptation (Example) Source Program Detour On-Ramp On-Ramp Off-Ramp Target Program Off-Ramp Formula global invariants (INV ) Ω2 target program (TSpec ) source program (SSpec ) Ω1 restriction (R INV Ω2 Ω1 SSpec ∧ ^ AReq * RCond * TSpec Cond ) Example AReq safe state INV All cars reach Off-Ramp SSpec All cars on road or detour AReq Construction finished RCond No cars enter the detour TSpec All cars on road 19/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik Guided Adaptation (Example) Source Program Detour On-Ramp On-Ramp Off-Ramp Target Program Off-Ramp Formula global invariants (INV ) Ω2 target program (TSpec ) source program (SSpec ) Ω1 restriction (R INV Ω2 Ω1 SSpec ∧ ^ AReq * RCond * TSpec Cond ) Example AReq safe state INV All cars reach Off-Ramp SSpec All cars on road or detour AReq Construction finished RCond No cars enter the detour TSpec All cars on road 19/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik Guided Adaptation (Example) Detour Source Program On-Ramp Off-Ramp m n adapt On-Ramp Target Program m Off-Ramp n Formula global invariants (INV ) Ω2 target program (TSpec ) source program (SSpec ) Ω1 restriction (R INV Ω2 Ω1 SSpec ∧ ^ AReq * RCond * TSpec Cond ) Example AReq safe state INV All cars reach Off-Ramp SSpec All cars on road or detour AReq Construction finished RCond No cars enter the detour TSpec All cars on road 19/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik Guided Adaptation (Example) Detour Source Program On-Ramp Off-Ramp m n adapt On-Ramp Target Program m Off-Ramp n Formula global invariants (INV ) Ω2 target program (TSpec ) source program (SSpec ) Ω1 restriction (R INV Ω2 Ω1 SSpec ∧ ^ AReq * RCond * TSpec Cond ) Example AReq safe state INV All cars reach Off-Ramp SSpec All cars on road or detour AReq Construction finished RCond No cars enter the detour TSpec All cars on road 19/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik Guided Adaptation (Example) On-Ramp Target Program Off-Ramp Formula global invariants (INV ) Ω2 target program (TSpec ) source program (SSpec ) Ω1 restriction (R INV Ω2 Ω1 SSpec ∧ ^ AReq * RCond * TSpec Cond ) Example AReq safe state INV All cars reach Off-Ramp SSpec All cars on road or detour AReq Construction finished RCond No cars enter the detour TSpec All cars on road 19/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik Guided Adaptation (Example) On-Ramp Target Program Off-Ramp Formula global invariants (INV ) Ω2 target program (TSpec ) source program (SSpec ) Ω1 restriction (R INV Ω2 Ω1 SSpec ∧ ^ AReq * RCond * TSpec Cond ) Example AReq safe state INV All cars reach Off-Ramp SSpec All cars on road or detour AReq Construction finished RCond No cars enter the detour TSpec All cars on road 19/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik Overlap Adaptation ! Ω2 Ω1 SSpec ∧ ^ AReq * RCond * true ∧ ! Ω1 Ω2 ^ AReq * TSpec ∧ RCond * true Ω2 source program (SSpec ) Ω1 restriction (R Cond ) AReq restriction (RCond ) Ω Ω1 2 target program (TSpec ) 20/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik Overlap Adaptation (Example) Source Program Detour On-Ramp Off-Ramp Formula INV Ω2 Ω1 SSpec ∧ ^ AReq * RCond * true Ω1 Ω2 ^ AReq * TSpec ∧ RCond * true Ω2 source program (SSpec ) Ω1 restriction (R Cond ) Example AReq target program (TSpec ) INV All cars reach Off-Ramp SSpec All cars on road or detour AReq Construction finished RCond No car enters the detour TSpec No car off the road 21/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik Overlap Adaptation (Example) Source Program Detour On-Ramp Off-Ramp Formula INV Ω2 Ω1 SSpec ∧ ^ AReq * RCond * true Ω1 Ω2 ^ AReq * TSpec ∧ RCond * true Ω2 source program (SSpec ) Ω1 restriction (R Cond ) Example AReq target program (TSpec ) INV All cars reach Off-Ramp SSpec All cars on road or detour AReq Construction finished RCond No car enters the detour TSpec No car off the road 21/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik Overlap Adaptation (Example) Detour Overlap On-Ramp Off-Ramp Formula INV Ω2 Ω1 SSpec ∧ ^ AReq * RCond * true Ω1 Ω2 ^ AReq * TSpec ∧ RCond * true Ω2 source program (SSpec ) Ω1 restriction (R Cond ) Example AReq target program (TSpec ) INV All cars reach Off-Ramp SSpec All cars on road or detour AReq Construction finished RCond No car enters the detour TSpec No car off the road 21/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik Overlap Adaptation (Example) Detour Overlap On-Ramp Off-Ramp Formula INV Ω2 Ω1 SSpec ∧ ^ AReq * RCond * true Ω1 Ω2 ^ AReq * TSpec ∧ RCond * true Ω2 source program (SSpec ) Ω1 restriction (R Cond ) Example AReq target program (TSpec ) INV All cars reach Off-Ramp SSpec All cars on road or detour AReq Construction finished RCond No car enters the detour TSpec No car off the road 21/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik Overlap Adaptation (Example) Detour Overlap On-Ramp Off-Ramp Formula INV Ω2 Ω1 SSpec ∧ ^ AReq * RCond * true Ω1 Ω2 ^ AReq * TSpec ∧ RCond * true Ω2 source program (SSpec ) Ω1 restriction (R Cond ) Example AReq target program (TSpec ) INV All cars reach Off-Ramp SSpec All cars on road or detour AReq Construction finished RCond No car enters the detour TSpec No car off the road 21/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik Overlap Adaptation (Example) Detour Overlap On-Ramp Off-Ramp Formula INV Ω2 Ω1 SSpec ∧ ^ AReq * RCond * true Ω1 Ω2 ^ AReq * TSpec ∧ RCond * true Ω2 source program (SSpec ) Ω1 restriction (R Cond ) Example AReq target program (TSpec ) INV All cars reach Off-Ramp SSpec All cars on road or detour AReq Construction finished RCond No car enters the detour TSpec No car off the road 21/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik Overlap Adaptation (Example) Target Program On-Ramp Off-Ramp Formula INV Ω2 Ω1 SSpec ∧ ^ AReq * RCond * true Ω1 Ω2 ^ AReq * TSpec ∧ RCond * true Ω2 source program (SSpec ) Ω1 restriction (R Cond ) Example AReq target program (TSpec ) INV All cars reach Off-Ramp SSpec All cars on road or detour AReq Construction finished RCond No car enters the detour TSpec No car off the road 21/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik Overlap Adaptation (Example) Target Program On-Ramp Off-Ramp Formula INV Ω2 Ω1 SSpec ∧ ^ AReq * RCond * true Ω1 Ω2 ^ AReq * TSpec ∧ RCond * true Ω2 source program (SSpec ) Ω1 restriction (R Cond ) Example AReq target program (TSpec ) INV All cars reach Off-Ramp SSpec All cars on road or detour AReq Construction finished RCond No car enters the detour TSpec No car off the road 21/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik Summary Adapt-Operator Extended LTL (A-LTL) Program Properties Global Invariants Point-Safety Properties Point-Liveness Properties Adaptation Properties One-Point Adaptation Guided Adaptation Overlap Adaptation Expressiveness of LTL and A-LTL (Bonus) 22/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik Conclusion Now we... have a notation for program transitions (S * T ) defined different adaptation semantics can check program phases independently using standard model checking techniques standard model checkers can be extended to verify adaptive software systems as well Deficiencies Supports Point-Safety and Point-Liveness Properties only Cyclic adaptations not possible as such Adaption of Specification and Program may differ Program state explosion No implementation available 23/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik Any Questions? ? 24/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik A-LTL-Expressiveness Point-Safety properties can be expressed with LTL only: true ¬η * ψ ≡ (¬η) U ψ Point-Liveness properties can be expressed in LTL only: Determine every possible order of events (must be finite!) Concatenate these events using the Until-Operator Insert Globally-Properties 25/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik Adapt-Operator in LTL (I) Example ( ¬η) ∧ (α → ^ β) (ΩS ,ΩT ) * ψ The simplest case: ψ occurs in the first state ΩT ψ ψ 26/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik Adapt-Operator in LTL (I) Example ( ¬η) ∧ (α → ^ β) (ΩS ,ΩT ) * ψ The simplest case: ψ occurs in the first state ΩT ψ ΩT ∧ ψ 26/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik Adapt-Operator in LTL (II) Example ( ¬η) ∧ (α → ^ β) (ΩS ,ΩT ) * ψ The easy case: α does not occur ΩS ¬α ΩT ψ (¬α) U ψ 27/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik Adapt-Operator in LTL (II) Example ( ¬η) ∧ (α → ^ β) (ΩS ,ΩT ) * ψ The easy case: α does not occur ΩS ¬α ΩT ψ (¬α) U(¬α ∧ ΩS ∧ X(ΩS ∧ ψ)) 27/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik Adapt-Operator in LTL (III) Example ( ¬η) ∧ (α → ^ β) (ΩS ,ΩT ) * ψ The general case: α must not occur after the last β ΩS β ¬α ΩT ψ ^(β ∧ X((¬α) U ψ)) 28/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik Adapt-Operator in LTL (III) Example ( ¬η) ∧ (α → ^ β) (ΩS ,ΩT ) * ψ The general case: α must not occur after the last β ΩS β ¬α ΩT ψ ^(β ∧ X((¬α) U(¬α ∧ ΩS ∧ X(ΩT ∧ ψ)))) 28/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik Adapt-Operator in LTL (IV) Example ( ¬η) ∧ (α → ^ β) (ΩS ,ΩT ) * ψ The special case: β holds in the last source state ΩS ΩT β ψ ^(β ∧ X ψ) 29/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik Adapt-Operator in LTL (IV) Example ( ¬η) ∧ (α → ^ β) (ΩS ,ΩT ) * ψ The special case: β holds in the last source state ΩS ΩT β ψ ^(β ∧ ΩS ∧ X(ΩT ∧ ψ)) 29/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik Adapt-Operator in LTL (V) Example ( ¬η) ∧ (α → ^ β) (ΩS ,ΩT ) * ψ Until now we have ΩT ∧ ψ ∨ (¬α) U(¬α ∧ ΩS ∧ X(ΩS ∧ ψ)) ∨ ^(β ∧ X((¬α) U((¬α) ∧ ΩS ∧ X(ΩT ∧ ψ)))) ∨ ^(β ∧ ΩS ∧ X(ωT ∧ ψ)) 30/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik Adapt-Operator in LTL (V) Example ( ¬η) ∧ (α → ^ β) (ΩS ,ΩT ) * ψ When also considering ¬η ΩT ∧ ψ ∨ (¬α ∧ ¬η) U(¬α ∧ ¬η ∧ ΩS ∧ X(ΩS ∧ ψ)) ∨ (¬η) U(β ∧ ¬η ∧ X((¬α ∧ ¬η) U(¬α ∧ ¬η ∧ ΩS ∧ X(ΩT ∧ ψ)))) ∨ (¬η) U(β ∧ ¬η ∧ ΩS ∧ X(ΩT ∧ ψ)) 30/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik Adapt-Operator in LTL (V) Example ( ¬η) ∧ (α → ^ β) (ΩS ,ΩT ) * ψ When also considering ¬η ΩT ∧ ψ ∨ (¬α ∧ ¬η) U(¬α ∧ ¬η ∧ ΩS ∧ X(ΩS ∧ ψ)) ∨ (¬η) U(β ∧ ¬η ∧ X((¬α ∧ ¬η) U(¬α ∧ ¬η ∧ ΩS ∧ X(ΩT ∧ ψ)))) ∨ (¬η) U(β ∧ ¬η ∧ ΩS ∧ X(ΩT ∧ ψ)) Ω ⇒ We stick to the ϕ * ψ syntax 30/31 Michael Kruse Fakultät für Elektrotechnik, Informatik und Mathematik Any Questions? ? 31/31