## Formal Methods Module II: Model Checking Ch. 09: **Timed and Hybrid Systems**

### Roberto Sebastiani

DISI, Università di Trento, Italy – roberto.sebastiani@unitn.it URL: http://disi.unitn.it/rseba/DIDATTICA/fm2021/

Teaching assistant:Giuseppe Spallitta– giuseppe.spallitta@unitn.it

### M.S. in Computer Science, Mathematics, & Artificial Intelligence Systems Academic year 2020-2021

last update: Thursday 27^{th}May, 2021, 13:27

Copyright notice: some material (text, figures) displayed in these slides is courtesy of R. Alur, M. Benerecetti, A. Cimatti, M. Di Natale, P. Pandya, M. Pistore, M. Roveri, C. Tinelli, and S.Tonetta, who detain its copyright. Some exampes displayed in these slides are taken from [Clarke, Grunberg & Peled, “Model Checking”, MIT Press], and their copyright is

detained by the authors. All the other material is copyrighted by Roberto Sebastiani. Every commercial use of this material is strictly forbidden by the copyright laws without the authorization of the authors. No copy of these slides can be

displayed in public without containing this copyright notice.

## Outline

1

### Motivations

2

### Timed systems: Modeling and Semantics Timed automata

3

### Symbolic Reachability for Timed Systems Making the state space finite

### Region automata Zone automata

4

### Hybrid Systems: Modeling and Semantics Hybrid automata

5

### Symbolic Reachability for Hybrid Systems Multi-Rate and Rectangular Hybrid Automata Linear Hybrid Automata

6

### Exercises

2 / 101

## Outline

1

### Motivations

2

### Timed systems: Modeling and Semantics Timed automata

3

### Symbolic Reachability for Timed Systems Making the state space finite

### Region automata Zone automata

4

### Hybrid Systems: Modeling and Semantics Hybrid automata

5

### Symbolic Reachability for Hybrid Systems Multi-Rate and Rectangular Hybrid Automata Linear Hybrid Automata

6

### Exercises

## Acknowledgments

### Thanks for providing material to:

### Rajeev Alur & colleagues (Penn University) Paritosh Pandya (IIT Bombay)

### Andrea Mattioli, Yusi Ramadian (Univ. Trento) Marco Di Natale (Scuola Superiore S.Anna, Italy)

### Disclaimer

### very introductory very-partial coverage

### mostly computer-science centric

4 / 101

## Hybrid Modeling

### Hybrid machines = State machines + Dynamic Systems

## Hybrid Modeling: Examples

### Automotive Applications Vehicle Coordination Protocols

### Interacting Autonomous Robots

### Bio-molecular Regulatory Networks

6 / 101

## Hybrid Modeling: Examples

### Automotive Applications Vehicle Coordination Protocols

### Interacting Autonomous Robots

### Bio-molecular Regulatory

### Networks

## Hybrid Modeling: Examples

### Automotive Applications Vehicle Coordination Protocols

### Interacting Autonomous Robots

### Bio-molecular Regulatory Networks

6 / 101

## Hybrid Modeling: Examples

### Automotive Applications Vehicle Coordination Protocols

### Interacting Autonomous Robots

### Bio-molecular Regulatory

### Networks

## Outline

1

### Motivations

2

### Timed systems: Modeling and Semantics Timed automata

3

### Symbolic Reachability for Timed Systems Making the state space finite

### Region automata Zone automata

4

### Hybrid Systems: Modeling and Semantics Hybrid automata

5

### Symbolic Reachability for Hybrid Systems Multi-Rate and Rectangular Hybrid Automata Linear Hybrid Automata

6

### Exercises

7 / 101

## Outline

1

### Motivations

2

### Timed systems: Modeling and Semantics Timed automata

3

### Symbolic Reachability for Timed Systems Making the state space finite

### Region automata Zone automata

4

### Hybrid Systems: Modeling and Semantics Hybrid automata

5

6

### Exercises

## Timed Automata

9 / 101

## Example: Simple light control

### Requirement:

### if Off and press is issued once, then the light switches on;

### if Off and press is issued twice quickly, then the light gets brighter;

### if Light/Bright and press is issued once, then the light switches off;

### =⇒ Cannot be achieved with standard automata

## Example: Simple light control

### Solution: add real-valued clock x x reset at first press

### if next press before x reaches 3 time units, then the light will get brighter;

### otherwise the light is turned off

10 / 101

## Modeling: timing constraints

### Finite graph + finite set of (real-valued) clocks

### Vertexes are locations Time can elapse there Constraints (invariants) Edges are switches

### Subject to constraints Reset clocks

### Meaning of clock value: time elapsed since the last time it was reset.

## Timed Automata

### Locations l

_{1}

### , l

_{2}

### , ... (like in standard automata) discrete part of the state

### may be implemented by discrete variables

### Switches (discrete transitions like in standard aut.) Labels, aka events, actions,... (like in standard aut.)

### used for synchronization Clocks: x, y,... ∈ Q

^{+}

### value: time elapsed since the last time it was reset Guards: (x ./ C) s.t. ./ ∈ {≤, <, ≥, >}, C ∈ N

### set of clock comparisons against integers bounds constrain the execution of the switch

### Resets (x := 0)

### set of clock assignments to 0

### Invariants: (x ./ C) s.t. ./ ∈ {≤, <, ≥, >}, C ∈ N set of clock comparisons against integers bounds ensure progress

a l1

l2

12 / 101

## Timed Automata

### Locations l

_{1}

### , l

_{2}

### , ... (like in standard automata) discrete part of the state

### may be implemented by discrete variables

### Switches (discrete transitions like in standard aut.) Labels, aka events, actions,... (like in standard aut.)

### used for synchronization Clocks : x, y,... ∈ Q

^{+}

### value: time elapsed since the last time it was reset Guards : (x ./ C) s.t. ./ ∈ {≤, <, ≥, >}, C ∈ N

### set of clock comparisons against integers bounds constrain the execution of the switch

### Resets (x := 0)

### set of clock assignments to 0

### Invariants: (x ./ C) s.t. ./ ∈ {≤, <, ≥, >}, C ∈ N set of clock comparisons against integers bounds ensure progress

(x ≥ 4) (y ≤ 2) a

y := 0 l1

l2

## Timed Automata

### Locations l

_{1}

### , l

_{2}

### , ... (like in standard automata) discrete part of the state

### may be implemented by discrete variables

### Switches (discrete transitions like in standard aut.) Labels, aka events, actions,... (like in standard aut.)

### used for synchronization Clocks: x, y,... ∈ Q

^{+}

### value: time elapsed since the last time it was reset Guards: (x ./ C) s.t. ./ ∈ {≤, <, ≥, >}, C ∈ N

### set of clock comparisons against integers bounds constrain the execution of the switch

### Resets (x := 0)

### set of clock assignments to 0

### Invariants : (x ./ C) s.t. ./ ∈ {≤, <, ≥, >}, C ∈ N set of clock comparisons against integers bounds ensure progress

(x ≥ 4) (y ≤ 2) a

y := 0 l1

(x ≤ 5)

l2

(x > 4) (y ≤ 3)

12 / 101

## Timed Automata: States and Transitions

### State: hl

_{i}

### , x , y i hl

_{1}

### , 4, 7i: OK!

### hl

_{2}

### , 2, 4i: not OK! (violates invariant in l

_{2}

### ) Switch: hl

_{i}

### , x , y i −→ hl

^{a}j

### , x

^{0}

### , y

^{0}

### i

### hl

_{1}

### , 4.5, 2i −→ hl

^{a}

_{2}

### , 4.5, 0i: OK!

### hl

_{1}

### , 6, 2i −→ hl

^{a}

_{2}

### , 6, 0i: not OK! (violates invar. in l

_{1}

### ) hl

_{1}

### , 3, 2i −→ hl

^{a}

_{2}

### , 3, 0i: not OK! (violates guard &

### invar. in l

_{2}

### )

### hl

_{1}

### , 4.5, 2i −→ hl

^{a}

_{2}

### , 4.5, 2i: not OK! (violates reset) hl

_{1}

### , 4, 2i −→ hl

^{a}

_{2}

### , 4, 0i: not OK! (violates invar. in l

_{2}

### )

### Wait (time elapse): hl

_{i}

### , x , y i −→ hl

^{δ}

_{i}

### , x + δ, y + δi hl

_{1}

### , 3, 0i −→ hl

^{2}

_{1}

### , 5, 2i: OK!

### hl

_{1}

### , 3, 0i −→ hl

^{3}

_{1}

### , 6, 3i: not OK! (violates invar. in l

1### )

(x ≥ 4) (y ≤ 2) a

y := 0 l1

(x ≤ 5)

l2

(x > 4) (y ≤ 3)

## Timed Automata: Formal Syntax

### Timed Automaton hL, L

^{0}

### , Σ, X , Φ(X ), E i L: Set of locations

### L

^{0}

### ⊆ L: Set of initial locations Σ: Set of labels

### X : Set of clocks Φ(X ): Set of invariants

### E ⊆ L × Σ × Φ(X ) × 2

^{X}

### × L: Set of switches A switch hl, a, ϕ, λ, l

^{0}

### i s.t.

### l : source location a: label

### ϕ: clock constraints λ ⊆ X : clocks to be reset l

^{0}

### : target location

(x ≥ 4) (y ≤ 2) a

y := 0 l1

(x ≤ 5)

l2

(x > 4) (y ≤ 3)

14 / 101

## Clock constraints and clock interpretations

### Grammar of clock constraints:

### ϕ ::= x ≤ C | x < C | x ≥ C | x > C | ϕ ∧ ϕ s.t. C positive integer values.

### =⇒ allow only comparison of a clock with a constant

### clock interpretation: ν

### X = hx , y , zi, ν = h1.0, 1.5, 0i clock interpretation ν after δ time: ν + δ

### δ = 0.2, ν + δ = h1.2, 1.7, 0.2i clock interpretation ν after reset λ: ν[λ]

### λ = {y }, ν[y := 0] = h1.0, 0, 0i

### A state for a timed automaton is a pair hl, νi, where l is a location and ν is a clock interpretation

(x ≥ 4) (y ≤ 2) a

y := 0 l1

(x ≤ 5)

l2

(x > 4) (y ≤ 3)

## Remark: why integer constants in clock constraints?

### The constant in clock constraints are assumed to be integer w.l.o.g.:

### if rationals, multiply them for their greatest common denominator, and change the time unit accordingly

### in practice, multiply by 10

^{k}

### (resp 2

^{k}

### ), k being the number of precision digits (resp. bits), and change the time unit accordingly Ex: 1.345, 0.78, 102.32 seconds

### =⇒ 1, 345, 780, 102, 320 milliseconds

16 / 101

## Example

### clocks {x , y } can be set/reset independently x is reset to 0 from s

_{0}

### to s

_{1}

### on a

### switches b and c happen within 1 time-unit from a because of constraints in s

_{1}

### and s

_{2}

### delay between b and the following d is > 2

### no explicit bounds on time difference between event c − d

## Timed Automata: Semantics

### Semantics of A defined in terms of a (infinite) transition system S

_{A}

^{def}

### = hQ, Q

^{0}

### , →, Σi

### Q: {hl, νi} s.t. l location and ν clock evaluation Q

^{0}

### : {hl, νi} s.t. l ∈ L

^{0}

### location and ν(X ) = 0

### →:

### state change due to location switch state change due to time elapse Σ : set of labels of Σ ∪ Q

^{+}

18 / 101

## State change in transition system

### Initial State

### hq, 0i

### Initial state

## State change in transition system

### Time elapse

### hq, 0i −→ hq, 1.2i

^{1.2}

### state change due to elapse of time

19 / 101

## State change in transition system

### Time Elapse, Switch and their Concatenation hq, 0i −→ hq, 1.2i

^{1.2}

### −→ hq

^{a}

^{0}

### , 1.2i ”wait δ; switch;”

### =⇒ hq, 0i

^{1.2+a}

### −→ hq

^{0}

### , 1.2i ”wait δ and switch;”

## State change in transition system

### Time Elapse, Switch and their Concatenation hq, 0i −→ hq, 1.2i

^{1.2}

### −→ hq

^{a}

^{0}

### , 1.2i ”wait δ; switch;”

### =⇒ hq, 0i

^{1.2+a}

### −→ hq

^{0}

### , 1.2i ”wait δ and switch;”

19 / 101

## Example

push push

click

### Switch may be turned on whenever at least 2 time units has elapsed since last “turn off”

### Light automatically switches off after 9 time units.

### Example execution

### hoff , 0, 0i −→ hoff , 3.5, 3.5i

^{3.5}

### −→ hon, 0, 0i

^{push}

### −→ hon, 3.14, 3.14i

^{3.14}

push

### −→ hon, 0, 3.14i −→ hon, 3, 6.14i

^{3}

### −→ hon, 5.86, 9i

^{2.86}

### −→ hoff , 0, 9i

^{click}

## Remark: Non-Zenoness

### Beware of Zeno! (paradox)

### When the invariant is violated some edge must be enabled

### Automata should admit the possibility of time to diverge

21 / 101

## Combination of Timed Automata

### Complex system = product of interacting systems Let A

_{1}

^{def}

### = hL

_{1}

### , L

^{0}

_{1}

### , Σ

_{1}

### , X

_{1}

### , Φ

_{1}

### (X

_{1}

### ), E

_{1}

### i,

### A

_{2}

^{def}

### = hL

_{2}

### , L

^{0}

_{2}

### , Σ

_{2}

### , X

_{2}

### , Φ

_{2}

### (X

_{2}

### ), E

_{2}

### i Product: A

_{1}

### ||A

_{2}

^{def}

### =

### hL

_{1}

### × L

_{2}

### , L

^{0}

_{1}

### × L

^{0}

_{2}

### , Σ

_{1}

### ∪ Σ

_{2}

### , X

_{1}

### ∪ X

_{2}

### , Φ

_{1}

### (X

_{1}

### ) ∪ Φ

_{2}

### (X

_{2}

### ), E

_{1}

### ||E

_{2}

### i Transition iff:

### Label a belongs to both alphabets =⇒ synchronized

### blocking synchronization: a-labeled switches cannot be shot alone Label a only in the alphabet of A

_{1}

### =⇒ asynchronized

### Label a only in the alphabet of A

_{2}

### =⇒ asynchronized

## Transition Product

### Σ

1def

### = {a, b}

### Σ

_{2}

^{def}

### = {a, c}

23 / 101

## Transition Product: Example

## Example: Train-gate controller [Alur CAV’99]

### Desired property: G(s

_{2}

### → t

_{2}

### )

25 / 101

## Train-gate controller: Product

## Outline

1

### Motivations

2

### Timed systems: Modeling and Semantics Timed automata

3

### Symbolic Reachability for Timed Systems Making the state space finite

### Region automata Zone automata

4

### Hybrid Systems: Modeling and Semantics Hybrid automata

5

6

### Exercises

27 / 101

## Outline

1

### Motivations

2

### Timed systems: Modeling and Semantics Timed automata

3

### Symbolic Reachability for Timed Systems Making the state space finite

### Region automata Zone automata

4

### Hybrid Systems: Modeling and Semantics Hybrid automata

5

6

### Exercises

## Reachability Analysis

### Verification of safety requirement: reachability problem

### Input: a timed automaton A and a set of target locations L

^{F}

### ⊆ L Problem: Determining whether L

^{F}

### is reachable in a timed automaton A

### A location l of A is reachable if some state q with location component l is a reachable state of the transition system S

_{A}

29 / 101

## Timed/hybrid Systems: problem

### Problem

### The system S

_{A}

### associated to A has infinitely-many states & symbols.

### Is finite state analysis possible?

### Is reachability problem decidable?

## Idea: Finite Partitioning

### Goal

### Partition the state space into finitely-many equivalence classes, so that equivalent states exhibit (bi)similar behaviors

31 / 101

## Reachability analysis

## Timed Vs Time-Abstract Relations

### Idea

### Infinite transition system associated with a timed/hybrid automaton A:

### S

_{A}

### : Labels on continuous steps are delays in Q

^{+}

### U

_{A}

### (time-abstract): actual delays are suppressed

### =⇒ all continuous steps have same label

### from ”wait δ and switch” to ”wait (sometime) and switch”

33 / 101

## Time-abstract transition system U _{A}

### U

_{A}

### (time-abstract): actual delays are suppressed Only change due to location switch stated explicitly Cut system to finitely many labels

### U

_{A}

### (instead of S

_{A}

### ) allows for capturing untimed properties (e.g., reachability, safety)

### Example

### A: (“wait δ; switch;”)

### hl

0### , 0, 0i −→ hl

^{1.2}0

### , 1.2, 1.2i −→ hl

^{a}1

### , 0, 1.2i −→ hl

^{0.7}1

### , 0.7, 1.9i −→

^{b}

### hl

2### , 0.7, 0i

### S

_{A}

### : (“wait δ and switch;”)

### hl

0### , 0, 0i

^{1.2+a}

### −→ hl

1### , 0, 1.2i

^{0.7+b}

### −→ hl

2### , 0.7, 0i

### U

_{A}

### : (“wait (sometime) and switch;”)

### hl

_{0}

### , 0, 0i −→ hl

^{a}

_{1}

### , 0, 1.2i −→ hl

^{b}

_{2}

### , 0.7, 0i

## Stable quotients

### Idea: Collapse states which are equivalent modulo “wait & switch”

### Cut to finitely many states Stable equivalence relation

### Quotient of U

_{A}

### = transition system [U

_{A}

### ]

35 / 101

## L ^{F} -sensitive equivalence relation

### All equivalent states in a class belong to either L

^{F}

### or not L

^{F}

### E.g.: states with different labels cannot be equivalent

## Stable Quotient: Intuitive example

### Task: plan trip from DISI to VR train station

### “take the next #5 bus to TN train station and then the 6pm train to VR”

### Constraints:

### It is 5.18pm

### Train to VR leaves at TN train station at 6.00pm it takes 3 minutes to walk from DISI to BUS stop Bus #5 passes 5.20pm or at 5.40pm

### Bus #5 takes 15 minutes to TN train station

### it takes 2 minutes to walk from BUS stop to TN train station Time-Abstract plan (U

A### ):

### “walk to bus stop; take 5.40 #5 bus to TN train-station stop;

### walk to train station; take the 6pm train to VR”

### Actual (implicit) plan (A):

### “wait δ

1### ; walk to bus stop; wait δ

2### ; take 5.40 #5 bus to TN train-station stop;

### wait δ

3### at bus stop; walk to train station; wait δ

4### ; take the 6pm train to VR”

### where δ

1### + δ

2### = 19min and δ

3### + δ

4### = 3min

All executions with distinct values of δi are bisimilar37 / 101

## Outline

1

### Motivations

2

### Timed systems: Modeling and Semantics Timed automata

3

### Symbolic Reachability for Timed Systems Making the state space finite

### Region automata Zone automata

4

### Hybrid Systems: Modeling and Semantics Hybrid automata

5

6

### Exercises

## Region Equivalence over clock interpretation

### Preliminary definitions & terminology Given a clock x :

### bxc is the integral part of x (ex: b3.7c = 3) fr(x) is the fractional part of x (ex: fr(3.7) = 0.7)

### C

_{x}

### is the maximum constant occurring in clock constraints x ./ C

x### Region Equivalence: ν ∼ = ν

^{0}

### Given a timed automaton A, two clock interpretations ν, ν

^{0}

### are region equivalent (ν ∼ = ν

^{0}

### ) iff all the following conditions hold:

### C1: For every clock x , either bν(x)c = bν

^{0}

### (x )c or bν(x)c, bν

^{0}

### (x )c ≥ C

x### C2: For every clock pair x , y s.t. ν(x ), ν

^{0}

### (x ) ≤ C

_{x}

### and ν(y ), ν

^{0}

### (y ) ≤ C

y### ,

### fr(ν(x)) ≤ fr(ν(y)) iff fr(ν

^{0}

### (x)) ≤ fr(ν

^{0}

### (y)) C3: For every clock x s.t. ν(x ), ν

^{0}

### (x ) ≤ C

x### fr(ν(x)) = 0 iff fr(ν

^{0}

### (x)) = 0

39 / 101

## Conditions: C1 + C2 + C3

C_{x}

x y

C_{y}

1 2 3 4

1 2 3

0

C1:

### For every clock x , either

bν(x)c = bν^{0}(x )c

### or

bν(x)c, bν^{0}(x )c ≥ Cx

C2:

### For every clock pair x , y s.t. ν(x ), ν

^{0}

### (x ) ≤ C

x### and ν(y ), ν

^{0}

### (y ) ≤ C

y### ,

fr(ν(x)) ≤ fr(ν(y)) iff fr(ν^{0}(x)) ≤ fr(ν

^{0}(y))

C3:

### For every clock x s.t. ν(x ), ν

^{0}

### (x ) ≤ C

x### ,

fr(ν(x)) = 0 iff fr(ν^{0}(x)) = 0

## Conditions: C1 + C2 + C3

C_{x}

x y

C_{y}

1 2 3 4

1 2 3

0

C1:

### For every clock x , either

bν(x)c = bν^{0}(x )c

### or

bν(x)c, bν^{0}(x )c ≥ Cx

C2:

### For every clock pair x , y s.t. ν(x ), ν

^{0}

### (x ) ≤ C

x### and ν(y ), ν

^{0}

### (y ) ≤ C

y### ,

fr(ν(x)) ≤ fr(ν(y)) iff fr(ν^{0}(x)) ≤ fr(ν

^{0}(y))

C3:

### For every clock x s.t. ν(x ), ν

^{0}

### (x ) ≤ C

x### ,

fr(ν(x)) = 0 iff fr(ν^{0}(x)) = 0

40 / 101

## Conditions: C1 + C2 + C3

C_{x}

x y

C_{y}

1 2 3 4

1 2 3

0

C1:

### For every clock x , either

bν(x)c = bν^{0}(x )c

### or

bν(x)c, bν^{0}(x )c ≥ Cx

C2:

### For every clock pair x , y s.t. ν(x ), ν

^{0}

### (x ) ≤ C

x### and ν(y ), ν

^{0}

### (y ) ≤ C

y### ,

fr(ν(x)) ≤ fr(ν(y)) iff fr(ν^{0}(x)) ≤ fr(ν

^{0}(y))

C3:

### For every clock x s.t. ν(x ), ν

^{0}

### (x ) ≤ C

x### ,

fr(ν(x)) = 0 iff fr(ν^{0}(x)) = 0

## Conditions: C1 + C2 + C3

C_{x}

x y

C_{y}

1 2 3 4

1 2 3

0

C1:

### For every clock x , either

bν(x)c = bν^{0}(x )c

### or

bν(x)c, bν^{0}(x )c ≥ Cx

C2:

### For every clock pair x , y s.t. ν(x ), ν

^{0}

### (x ) ≤ C

x### and ν(y ), ν

^{0}

### (y ) ≤ C

y### ,

fr(ν(x)) ≤ fr(ν(y)) iff fr(ν^{0}(x)) ≤ fr(ν

^{0}(y))

C3:

### For every clock x s.t. ν(x ), ν

^{0}

### (x ) ≤ C

x### ,

fr(ν(x)) = 0 iff fr(ν^{0}(x)) = 0

40 / 101

## Regions, intuitive idea:

C_{x}

x y

C_{y}

1 2 3 4

1 2 3

0

### Intuition: ν ∼ = ν

^{0}

### iff they satisfy the same set of constraints in the form

### x

_{i}

### < c, x

_{i}

### > c, x

_{i}

### = c, x

_{i}

### − x

_{j}

### < c, x

_{i}

### − x

_{j}

### > c, x

_{i}

### − x

_{j}

### = c

### s.t. c ≤ C

_{x}

_{i}

## Region Operations

42 / 101

## Properties of Regions

### The region equivalence relation ∼ = is a time-abstract bisimulation:

### Action transitions: if ν ∼ = µ and hl, νi −→ hl

^{a}

^{0}

### , ν

^{0}

### i for some l

^{0}

### , ν

^{0}

### , then there exists µ

^{0}

### s.t. ν

^{0}

### ∼ = µ

^{0}

### and hl, µi −→ hl

^{a}

^{0}

### , µ

^{0}

### i

### Wait transitions: if ν ∼ = µ,

### then for every δ ∈ Q

^{+}

### there exists δ

^{0}

### ∈ Q

^{+}

### s.t. ν + δ ∼ = µ + δ

^{0}

### =⇒ If ν ∼ = µ, then hl, νi and hl, µi satisfy the same temporal-logic

### formulas

## Time-abstract Bisimulation in Regions

### C

_{x}

### x y

### C

_{y}

### 1 2 3 4

### 1 2 3

### 0

44 / 101

## Time-abstract Bisimulation in Regions

### C

_{x}

### x y

### C

_{y}

### 1 2 3 4

### 1 2 3

### 0

## Time-abstract Bisimulation in Regions

### C

_{x}

### x y

### C

_{y}

### 1 2 3 4

### 1 2 3

### 0

44 / 101

## Time-abstract Bisimulation in Regions

### C

_{x}

### x y

### C

_{y}

### 1 2 3 4

### 1 2 3

### 0

## Time-abstract Bisimulation in Regions

### C

_{x}

### x y

### C

_{y}

### 1 2 3 4

### 1 2 3

### 0

44 / 101

## Time-abstract Bisimulation in Regions

### C

_{x}

### x y

### C

_{y}

### 1 2 3 4

### 1 2 3

### 0

## Time-abstract Bisimulation in Regions

### C

_{x}

### x y

### C

_{y}

### 1 2 3 4

### 1 2 3

### 0

44 / 101

## Time-abstract Bisimulation in Regions

### C

_{x}

### x y

### C

_{y}

### 1 2 3 4

### 1 2 3

### 0

## Time-abstract Bisimulation in Regions

### C

_{x}

### x y

### C

_{y}

### 1 2 3 4

### 1 2 3

### 0

44 / 101

## Time-abstract Bisimulation in Regions

### C

_{x}

### x y

### C

_{y}

### 1 2 3 4

### 1 2 3

### 0

## Time-abstract Bisimulation in Regions

### C

_{x}

### x y

### C

_{y}

### 1 2 3 4

### 1 2 3

### 0

44 / 101

## Time-abstract Bisimulation in Regions

### C

_{x}

### x y

### C

_{y}

### 1 2 3 4

### 1 2 3

### 0

## Time-abstract Bisimulation in Regions

### C

_{x}

### x y

### C

_{y}

### 1 2 3 4

### 1 2 3

### 0

44 / 101

## Time-abstract Bisimulation in Regions

### C

_{x}

### x y

### C

_{y}

### 1 2 3 4

### 1 2 3

### 0

## Time-abstract Bisimulation in Regions

### C

_{x}

### x y

### C

_{y}

### 1 2 3 4

### 1 2 3

### 0

44 / 101

## Time-abstract Bisimulation in Regions

### C

_{x}

### x y

### C

_{y}

### 1 2 3 4

### 1 2 3

### 0

## Time-abstract Bisimulation in Regions

### C

_{x}

### x y

### C

_{y}

### 1 2 3 4

### 1 2 3

### 0

44 / 101

## Number of Clock Regions

### Clock region: equivalence class of clock interpretations Number of clock regions upper-bounded by

### k ! · 2

^{k}

### · Π

_{x ∈X}

### (2 · C

x### + 2), s.t. k

^{def}

### = ||X ||

### finite!

### exponential in the number of clocks grows with the values of C

_{x}

### Example

### 2 clocks x,y, C

x### = 2, C

y### = 1 8 open regions

### 14 open line segments 6 corner points

### =⇒ 28 regions

### < 2 · 2

^{2}

### · (2 · 2 + 2) · (2 · 1 + 2) = 192

## Region automaton

### Equivalent states = identical location + ∼ =-equivalent evaluations Equivalent Classes (regions): finite, stable, L

^{F}

### -sensitive

### R(A): Region automaton of A

### States: hl, r (A)i s.t. r (A) regions of A

### =⇒ Finite state automaton!

### Reachability problem hA, L

^{F}

### i =⇒ Reachability problem hR(A), L

^{F}

### i

### =⇒ Reachability in timed automata reduced to that in finite automata!

46 / 101

## Example: Region graph of a simple timed automata

### May be further reduced (e.g., collapsing B, C, D into one state)

## Complexity of Reasoning with Timed Automata

### Reachability in Timed Automata Decidable!

### Linear with number of locations Exponential in the number of clocks Grows with the values of C

_{x}

### Overall, PSPACE-Complete

### Language-containment with Timed Automata Undecidable!

48 / 101

## Outline

1

### Motivations

2

### Timed systems: Modeling and Semantics Timed automata

3

### Symbolic Reachability for Timed Systems Making the state space finite

### Region automata Zone automata

4

### Hybrid Systems: Modeling and Semantics Hybrid automata

5

6

### Exercises

## Zone Automata

### Collapse regions by convex unions of clock regions

### Clock Zone ϕ: set/conjunction of clock constraints in the form (x

_{i}

### ./ c), (x

_{i}

### − x

_{j}

### ./ c) , ./ ∈ {>, <, =, ≥, ≤}, c ∈ Z

### ϕ is a convex set in the k-dimensional euclidean space possibly unbounded

### =⇒ Contains all possible relationship for all clock value in a set Symbolic state: hl, ϕi

### l: location ϕ: clock zone

x y

50 / 101

## Zone Automata

### Definition: Zone Automaton

### Given a Timed Automaton A

^{def}

### = hL, L

^{0}

### , Σ, X , Φ(X ), E i,

### the Zone Automaton Z(A) is a transition system hQ, Q

^{0}

### , Σ, →i s.t.

### Q: set of all symbolic states of A (a symbolic state is hl, ϕi) Q

^{0}

^{def}

### = {hl, [X := 0]i | l ∈ L

^{0}

### }

### Σ: set of labels/events in A

### →: set of “wait&switch” symbolic transitions, in the form:

### hl, ϕi −→ hl

^{a}

^{0}

### , succ(ϕ, e)i

### succ(ϕ, e): successor of ϕ after (waiting and) executing the switch e

^{def}

### = hl, a, ψ, λ, l

^{0}

### i

### succ(hl, ϕi, e)

^{def}

### = hl

^{0}

### , succ(ϕ, e)i

## Zone Automata: Symbolic Transitions

### Definition: succ(ϕ, e)

### Let e

^{def}

### = hl, a, ψ, λ, l

^{0}

### i, and φ, φ

^{0}

### the invariants in l, l

^{0}

### Then

### succ(ϕ, e)

^{def}

### = (((ϕ ∧ φ)⇑ ∧φ) ∧ ψ)[λ := 0]

### ∧: standard conjunction/intersection

### ⇑: projection to infinity: ψ⇑

^{def}

### = {ν + δ | ν ∈ ψ, δ ∈ [0, +∞)}

### [λ := 0]: reset projection: ψ[λ := 0]

^{def}

### = {ν[λ := 0] | ν ∈ ψ}

### note: ϕ is considered “immediately before entering l”

52 / 101

## Zone Automata: Symbolic Transitions (cont.)

### Initial zone: values before entering the location

### Intersection with invariant φ: values allowed to enter the location

### Projection to infinity: values allowed to enter the location, after waiting unbounded time Intersection with invariant φ: values allowed to enter the location, after waiting a legal amount of time

### Intersection with guard ψ: values allowed to enter the location, after waiting a legal amount of time, from which the switch can be shot

### Reset projection λ: values ..., after reset

=⇒ Final!

## succ(ϕ, e) =

^{def}

## (((ϕ ∧ φ)⇑ ∧φ) ∧ ψ)[λ := 0]

## Zone Automata: Symbolic Transitions (cont.)

### Initial zone: values before entering the location

### Intersection with invariant φ: values allowed to enter the location

### Projection to infinity: values allowed to enter the location, after waiting unbounded time Intersection with invariant φ: values allowed to enter the location, after waiting a legal amount of time

### Intersection with guard ψ: values allowed to enter the location, after waiting a legal amount of time, from which the switch can be shot

### Reset projection λ: values ..., after reset

=⇒ Final!

ϕ

## succ(ϕ, e) =

^{def}

## (((ϕ ∧ φ)⇑ ∧φ) ∧ ψ)[λ := 0]

53 / 101

## Zone Automata: Symbolic Transitions (cont.)

### Initial zone: values before entering the location

### Intersection with invariant φ: values allowed

to enter the location### Projection to infinity: values allowed to enter the location, after waiting unbounded time Intersection with invariant φ: values allowed to enter the location, after waiting a legal amount of time

### Intersection with guard ψ: values allowed to enter the location, after waiting a legal amount of time, from which the switch can be shot

### Reset projection λ: values ..., after reset

=⇒ Final!

ϕ φ

## succ(ϕ, e) =

^{def}

## (((ϕ ∧ φ) ⇑ ∧φ) ∧ ψ)[λ := 0]

## Zone Automata: Symbolic Transitions (cont.)

### Initial zone: values before entering the location

### Intersection with invariant φ: values allowed to enter the location

### Reset projection λ: values ..., after reset

=⇒ Final!

## succ(ϕ, e) =

^{def}

## (((ϕ ∧ φ) ⇑ ∧φ) ∧ ψ)[λ := 0]

53 / 101

## Zone Automata: Symbolic Transitions (cont.)

### Initial zone: values before entering the location

### Intersection with invariant φ: values allowed to enter the location

### Reset projection λ: values ..., after reset

=⇒ Final!

## succ(ϕ, e) =

^{def}

## (((ϕ ∧ φ)⇑ ∧φ) ∧ ψ)[λ := 0]

## Zone Automata: Symbolic Transitions (cont.)

### Initial zone: values before entering the location

### Intersection with invariant φ: values allowed to enter the location

### Projection to infinity: values allowed to enter the location, after waiting unbounded time Intersection with invariant φ: values allowed

to enter the location, after waiting a legal amount of time### Reset projection λ: values ..., after reset

=⇒ Final!

φ

## succ(ϕ, e) =

^{def}

## (((ϕ ∧ φ)⇑ ∧φ) ∧ ψ)[λ := 0]

53 / 101

## Zone Automata: Symbolic Transitions (cont.)

### Initial zone: values before entering the location

### Intersection with invariant φ: values allowed to enter the location

### Reset projection λ: values ..., after reset

=⇒ Final!

## succ(ϕ, e) =

^{def}

## (((ϕ ∧ φ)⇑ ∧φ) ∧ ψ)[λ := 0]

## Zone Automata: Symbolic Transitions (cont.)

### Initial zone: values before entering the location

### Intersection with invariant φ: values allowed to enter the location

### Intersection with guard ψ: values allowed to

enter the location, after waiting a legal amount of time, from which the switch can be shot### Reset projection λ: values ..., after reset

=⇒ Final!

ψ

## succ(ϕ, e) =

^{def}

## (((ϕ ∧ φ)⇑ ∧φ) ∧ ψ)[λ := 0]

53 / 101

## Zone Automata: Symbolic Transitions (cont.)

### Initial zone: values before entering the location

### Intersection with invariant φ: values allowed to enter the location

### Reset projection λ: values ..., after reset

=⇒ Final!

## succ(ϕ, e) =

^{def}

## (((ϕ ∧ φ)⇑ ∧φ) ∧ ψ)[λ := 0]

## Zone Automata: Symbolic Transitions (cont.)

### Initial zone: values before entering the location

### Intersection with invariant φ: values allowed to enter the location

### Reset projection λ: values ..., after reset

=⇒ Final!

## succ(ϕ, e) =

^{def}

## (((ϕ ∧ φ)⇑ ∧φ) ∧ ψ)[λ := 0]

53 / 101

## Zone Automata: Symbolic Transitions (cont.)

### Initial zone: values before entering the location

### Intersection with invariant φ: values allowed to enter the location

### Reset projection λ: values ..., after reset

=⇒ Final!

## succ(ϕ, e) =

^{def}

## (((ϕ ∧ φ)⇑ ∧φ) ∧ ψ)[λ := 0]

## Zone Automata: Symbolic Transitions (cont.)

### Initial zone: values before entering the location

### Intersection with invariant φ: values allowed to enter the location

### Reset projection λ: values ..., after reset

=⇒ Final!

## succ(ϕ, e) =

^{def}

## (((ϕ ∧ φ)⇑ ∧φ) ∧ ψ)[λ := 0]

53 / 101

## Example: Zone Automata, Symbolic Transitions

### Initial zone: (x ≥ 0) ∧ (x ≤ 2) ∧

(y ≥ 0) ∧ (y ≤ 3) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2)

### Intersection with invariant φ : (y ≥ 1) ∧ (y ≤ 5)

### =⇒ (x ≥ 0) ∧ (x ≤ 2) ∧ (y ≥ 1) ∧ (y ≤ 3) ∧ (y − x ≤ 2)

### Projection to infinity:

=⇒ (x ≥ 0) ∧ (y ≥ 1) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2)

### Intersection with invariant φ: (y ≥ 1) ∧ (y ≤ 5)

### =⇒ (x ≥ 0) ∧ (y ≥ 1) ∧ (y ≤ 5) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2) Intersection with guard ψ : (y ≥ 4)

### =⇒ (y ≥ 4) ∧ (y ≤ 5) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2) Reset projection λ

^{def}

### = {y := 0}

### =⇒ (x ≥ 2) ∧ (x ≤ 6) ∧ (y ≥ 0) ∧ (y ≤ 0)

=⇒ Final!

## Example: Zone Automata, Symbolic Transitions

### Initial zone: (x ≥ 0) ∧ (x ≤ 2) ∧

### (y ≥ 0) ∧ (y ≤ 3) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2) Intersection with invariant φ : (y ≥ 1) ∧ (y ≤ 5)

### =⇒ (x ≥ 0) ∧ (x ≤ 2) ∧ (y ≥ 1) ∧ (y ≤ 3) ∧ (y − x ≤ 2)

### Projection to infinity:

=⇒ (x ≥ 0) ∧ (y ≥ 1) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2)

### Intersection with invariant φ: (y ≥ 1) ∧ (y ≤ 5)

### =⇒ (x ≥ 0) ∧ (y ≥ 1) ∧ (y ≤ 5) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2) Intersection with guard ψ : (y ≥ 4)

### =⇒ (y ≥ 4) ∧ (y ≤ 5) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2) Reset projection λ

^{def}

### = {y := 0}

### =⇒ (x ≥ 2) ∧ (x ≤ 6) ∧ (y ≥ 0) ∧ (y ≤ 0)

=⇒ Final!

ϕ

54 / 101

## Example: Zone Automata, Symbolic Transitions

### Initial zone: (x ≥ 0) ∧ (x ≤ 2) ∧

### (y ≥ 0) ∧ (y ≤ 3) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2) Intersection with invariant φ : (y ≥ 1) ∧ (y ≤ 5)

=⇒ (x ≥ 0) ∧ (x ≤ 2) ∧ (y ≥ 1) ∧ (y ≤ 3) ∧ (y − x ≤ 2)

### Projection to infinity:

=⇒ (x ≥ 0) ∧ (y ≥ 1) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2)

### Intersection with invariant φ: (y ≥ 1) ∧ (y ≤ 5)

### =⇒ (x ≥ 0) ∧ (y ≥ 1) ∧ (y ≤ 5) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2) Intersection with guard ψ : (y ≥ 4)

### =⇒ (y ≥ 4) ∧ (y ≤ 5) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2) Reset projection λ

^{def}

### = {y := 0}

### =⇒ (x ≥ 2) ∧ (x ≤ 6) ∧ (y ≥ 0) ∧ (y ≤ 0)

=⇒ Final!

ϕ φ

## Example: Zone Automata, Symbolic Transitions

### Initial zone: (x ≥ 0) ∧ (x ≤ 2) ∧

### (y ≥ 0) ∧ (y ≤ 3) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2) Intersection with invariant φ : (y ≥ 1) ∧ (y ≤ 5)

### =⇒ (x ≥ 0) ∧ (x ≤ 2) ∧ (y ≥ 1) ∧ (y ≤ 3) ∧ (y − x ≤ 2)

### Projection to infinity:

=⇒ (x ≥ 0) ∧ (y ≥ 1) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2)

### Intersection with invariant φ: (y ≥ 1) ∧ (y ≤ 5)

### =⇒ (x ≥ 0) ∧ (y ≥ 1) ∧ (y ≤ 5) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2) Intersection with guard ψ : (y ≥ 4)

### =⇒ (y ≥ 4) ∧ (y ≤ 5) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2) Reset projection λ

^{def}

### = {y := 0}

### =⇒ (x ≥ 2) ∧ (x ≤ 6) ∧ (y ≥ 0) ∧ (y ≤ 0)

=⇒ Final!

54 / 101

## Example: Zone Automata, Symbolic Transitions

### Initial zone: (x ≥ 0) ∧ (x ≤ 2) ∧

### (y ≥ 0) ∧ (y ≤ 3) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2) Intersection with invariant φ : (y ≥ 1) ∧ (y ≤ 5)

### =⇒ (x ≥ 0) ∧ (x ≤ 2) ∧ (y ≥ 1) ∧ (y ≤ 3) ∧ (y − x ≤ 2)

### Projection to infinity:

### =⇒ (x ≥ 0) ∧ (y ≥ 1) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2)

### Intersection with invariant φ: (y ≥ 1) ∧ (y ≤ 5)

### =⇒ (x ≥ 0) ∧ (y ≥ 1) ∧ (y ≤ 5) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2) Intersection with guard ψ : (y ≥ 4)

### =⇒ (y ≥ 4) ∧ (y ≤ 5) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2) Reset projection λ

^{def}

### = {y := 0}

### =⇒ (x ≥ 2) ∧ (x ≤ 6) ∧ (y ≥ 0) ∧ (y ≤ 0)

=⇒ Final!

## Example: Zone Automata, Symbolic Transitions

### Initial zone: (x ≥ 0) ∧ (x ≤ 2) ∧

### (y ≥ 0) ∧ (y ≤ 3) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2) Intersection with invariant φ : (y ≥ 1) ∧ (y ≤ 5)

### =⇒ (x ≥ 0) ∧ (x ≤ 2) ∧ (y ≥ 1) ∧ (y ≤ 3) ∧ (y − x ≤ 2)

### Projection to infinity:

### =⇒ (x ≥ 0) ∧ (y ≥ 1) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2)

### Intersection with invariant φ: (y ≥ 1) ∧ (y ≤ 5)

=⇒ (x ≥ 0) ∧ (y ≥ 1) ∧ (y ≤ 5) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2)

### Intersection with guard ψ : (y ≥ 4)

### =⇒ (y ≥ 4) ∧ (y ≤ 5) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2) Reset projection λ

^{def}

### = {y := 0}

### =⇒ (x ≥ 2) ∧ (x ≤ 6) ∧ (y ≥ 0) ∧ (y ≤ 0)

=⇒ Final!

φ

54 / 101

## Example: Zone Automata, Symbolic Transitions

### Initial zone: (x ≥ 0) ∧ (x ≤ 2) ∧

### (y ≥ 0) ∧ (y ≤ 3) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2) Intersection with invariant φ : (y ≥ 1) ∧ (y ≤ 5)

### =⇒ (x ≥ 0) ∧ (x ≤ 2) ∧ (y ≥ 1) ∧ (y ≤ 3) ∧ (y − x ≤ 2)

### Projection to infinity:

### =⇒ (x ≥ 0) ∧ (y ≥ 1) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2)

### Intersection with invariant φ: (y ≥ 1) ∧ (y ≤ 5)

### =⇒ (x ≥ 0) ∧ (y ≥ 1) ∧ (y ≤ 5) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2) Intersection with guard ψ : (y ≥ 4)

### =⇒ (y ≥ 4) ∧ (y ≤ 5) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2) Reset projection λ

^{def}

### = {y := 0}

### =⇒ (x ≥ 2) ∧ (x ≤ 6) ∧ (y ≥ 0) ∧ (y ≤ 0)

=⇒ Final!

## Example: Zone Automata, Symbolic Transitions

### Initial zone: (x ≥ 0) ∧ (x ≤ 2) ∧

### (y ≥ 0) ∧ (y ≤ 3) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2) Intersection with invariant φ : (y ≥ 1) ∧ (y ≤ 5)

### =⇒ (x ≥ 0) ∧ (x ≤ 2) ∧ (y ≥ 1) ∧ (y ≤ 3) ∧ (y − x ≤ 2)

### Projection to infinity:

### =⇒ (x ≥ 0) ∧ (y ≥ 1) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2)

### Intersection with invariant φ: (y ≥ 1) ∧ (y ≤ 5)

### =⇒ (x ≥ 0) ∧ (y ≥ 1) ∧ (y ≤ 5) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2) Intersection with guard ψ : (y ≥ 4)

=⇒ (y ≥ 4) ∧ (y ≤ 5) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2)

### Reset projection λ

^{def}

### = {y := 0}

### =⇒ (x ≥ 2) ∧ (x ≤ 6) ∧ (y ≥ 0) ∧ (y ≤ 0)

=⇒ Final!

ψ

54 / 101

## Example: Zone Automata, Symbolic Transitions

### Initial zone: (x ≥ 0) ∧ (x ≤ 2) ∧

### (y ≥ 0) ∧ (y ≤ 3) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2) Intersection with invariant φ : (y ≥ 1) ∧ (y ≤ 5)

### =⇒ (x ≥ 0) ∧ (x ≤ 2) ∧ (y ≥ 1) ∧ (y ≤ 3) ∧ (y − x ≤ 2)

### Projection to infinity:

### =⇒ (x ≥ 0) ∧ (y ≥ 1) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2)

### Intersection with invariant φ: (y ≥ 1) ∧ (y ≤ 5)

### =⇒ (x ≥ 0) ∧ (y ≥ 1) ∧ (y ≤ 5) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2) Intersection with guard ψ : (y ≥ 4)

### =⇒ (y ≥ 4) ∧ (y ≤ 5) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2) Reset projection λ

^{def}

### = {y := 0}

### =⇒ (x ≥ 2) ∧ (x ≤ 6) ∧ (y ≥ 0) ∧ (y ≤ 0)

=⇒ Final!

## Example: Zone Automata, Symbolic Transitions

### Initial zone: (x ≥ 0) ∧ (x ≤ 2) ∧

### (y ≥ 0) ∧ (y ≤ 3) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2) Intersection with invariant φ : (y ≥ 1) ∧ (y ≤ 5)

### =⇒ (x ≥ 0) ∧ (x ≤ 2) ∧ (y ≥ 1) ∧ (y ≤ 3) ∧ (y − x ≤ 2)

### Projection to infinity:

### =⇒ (x ≥ 0) ∧ (y ≥ 1) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2)

### Intersection with invariant φ: (y ≥ 1) ∧ (y ≤ 5)

### =⇒ (x ≥ 0) ∧ (y ≥ 1) ∧ (y ≤ 5) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2) Intersection with guard ψ : (y ≥ 4)

### =⇒ (y ≥ 4) ∧ (y ≤ 5) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2) Reset projection λ

^{def}

### = {y := 0}

=⇒ (x ≥ 2) ∧ (x ≤ 6) ∧ (y ≥ 0) ∧ (y ≤ 0)

=⇒ Final!

54 / 101

## Example: Zone Automata, Symbolic Transitions

### Initial zone: (x ≥ 0) ∧ (x ≤ 2) ∧

### (y ≥ 0) ∧ (y ≤ 3) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2) Intersection with invariant φ : (y ≥ 1) ∧ (y ≤ 5)

### =⇒ (x ≥ 0) ∧ (x ≤ 2) ∧ (y ≥ 1) ∧ (y ≤ 3) ∧ (y − x ≤ 2)

### Projection to infinity:

### =⇒ (x ≥ 0) ∧ (y ≥ 1) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2)

### Intersection with invariant φ: (y ≥ 1) ∧ (y ≤ 5)

### =⇒ (x ≥ 0) ∧ (y ≥ 1) ∧ (y ≤ 5) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2) Intersection with guard ψ : (y ≥ 4)

### =⇒ (y ≥ 4) ∧ (y ≤ 5) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2) Reset projection λ

^{def}

### = {y := 0}

### =⇒ (x ≥ 2) ∧ (x ≤ 6) ∧ (y ≥ 0) ∧ (y ≤ 0)

=⇒ Final!

## Example: Zone Automata, Symbolic Transitions

### Initial zone: (x ≥ 0) ∧ (x ≤ 2) ∧

### (y ≥ 0) ∧ (y ≤ 3) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2) Intersection with invariant φ : (y ≥ 1) ∧ (y ≤ 5)

### =⇒ (x ≥ 0) ∧ (x ≤ 2) ∧ (y ≥ 1) ∧ (y ≤ 3) ∧ (y − x ≤ 2)

### Projection to infinity:

### =⇒ (x ≥ 0) ∧ (y ≥ 1) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2)

### Intersection with invariant φ: (y ≥ 1) ∧ (y ≤ 5)

### =⇒ (x ≥ 0) ∧ (y ≥ 1) ∧ (y ≤ 5) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2) Intersection with guard ψ : (y ≥ 4)

### =⇒ (y ≥ 4) ∧ (y ≤ 5) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2) Reset projection λ

^{def}

### = {y := 0}

### =⇒ (x ≥ 2) ∧ (x ≤ 6) ∧ (y ≥ 0) ∧ (y ≤ 0)

=⇒ Final!

54 / 101

## Remark on succ(ϕ, e)

### In the above definition of succ(ϕ, e), ϕ is considered

### “immediately before entering l”:

### succ(ϕ, e)

^{def}

### = (((ϕ ∧ φ)⇑ ∧φ) ∧ ψ)[λ := 0]

### Alternative definition of succ(ϕ, e), ϕ is considered “immediately after entering l”:

### succ(ϕ, e)

^{def}

### = (((ϕ⇑ ∧φ) ∧ ψ)[λ := 0] ∧ φ

^{0}

### )

### no initial intersection with the invariant φ of source location l

### (here ϕ is assumed to be already the result of such intersection)

### final intersection with the invariant φ

^{0}

### of target location l

^{0}

## Symbolic Reachability Analysis

### 1: **function Reachable (A, L**

^{F}

### ) // A

^{def}

### = hL, L

^{0}

### , Σ, X , Φ(X ), E i

### 2: Reachable = ∅

### 3: Frontier = {hl

_{i}

### , {X = 0}i | l

_{i}

### ∈ L

^{0}

### }

### 4: **while (Frontier** **6= ∅) do**

### 5: extract hl, ϕi from Frontier

### 6: **if (l ∈ L**

^{F}

### and ϕ 6= ⊥) **then**

### 7: **return True**

### 8: **end if**

### 9: **if (6 ∃ hl, ϕ**

^{0}

### i ∈ Reachable s.t. ϕ ⊆ ϕ

^{0}

### ) **then**

### 10: add hl, ϕi to Reachable

### 11: **for e ∈ outcoming(l) do**

### 12: add succ(ϕ, e) to Frontier

### 13: **end for**

### 14: **end if**

### 15: **end while**

### 16: **return False**

56 / 101

## Canonical Data-structures for Zones: DBMs

### Difference-bound Matrices (DBMs) Matrix representation of constraints

### bounds on a single clock differences between 2 clocks

### Reduced form computed by all-pairs shortest path algorithm (e.g. Floyd-Warshall)

### Reduced DBM is canonical:

### equivalent sets of constraints produce the same reduced DBM Operations s.a reset, time-successor, inclusion, intersection are efficient

### =⇒ Popular choice in timed-automata-based tools

## Difference-bound matrices, DBMs

### DBM: matrix (k + 1) × (k + 1), k being the number of clocks added an implicit fake variable x

_{0}

^{def}

### = 0 s.t. x

_{i}

### ./ c =⇒ x

_{i}

### − x

_{0}

### ./ c each element is a pair (value,{0, 1}), s.t “{0, 1}” means “{<, ≤}”

### Example:

### (0 ≤ x

1### ) ∧(0 < x

2### ) ∧(x

1### < 2) ∧(x

2### < 1) ∧(x

1### − x

2### ≥ 0)

(x0− x1≤ 0) ∧(x0− x2<0) ∧(x1− x0<2) ∧(x2− x0<1) ∧(x2− x1≤ 0)58 / 101

## Difference-bound matrices, DBMs

### DBM: matrix (k + 1) × (k + 1), k being the number of clocks added an implicit fake variable x

_{0}

^{def}

### = 0 s.t. x

_{i}

### ./ c =⇒ x

_{i}

### − x

_{0}

### ./ c each element is a pair (value,{0, 1}), s.t “{0, 1}” means “{<, ≤}”

### Example:

### (0 ≤ x

1### ) ∧(0 < x

2### ) ∧(x

1### < 2) ∧(x

2### < 1) ∧(x

1### − x

2### ≥ 0)

(x0− x1≤ 0) ∧(x0− x2<0) ∧(x1− x0<2) ∧(x2− x0<1) ∧(x2− x1≤ 0)## Difference-bound matrices, DBMs

### DBM: matrix (k + 1) × (k + 1), k being the number of clocks added an implicit fake variable x

_{0}

^{def}

### = 0 s.t. x

_{i}

### ./ c =⇒ x

_{i}

### − x

_{0}

### ./ c each element is a pair (value,{0, 1}), s.t “{0, 1}” means “{<, ≤}”

### Example:

### (0 ≤ x

1### ) ∧(0 < x

2### ) ∧(x

1### < 2) ∧(x

2### < 1) ∧(x

1### − x

2### ≥ 0) (x

0### − x

1### ≤ 0) ∧(x

0### − x

2### < 0) ∧(x

1### − x

0### < 2) ∧(x

2### − x

0### < 1) ∧(x

2### − x

1### ≤ 0)

58 / 101

## Difference-bound matrices, DBMs

### DBM: matrix (k + 1) × (k + 1), k being the number of clocks added an implicit fake variable x

_{0}

^{def}

### = 0 s.t. x

_{i}

### ./ c =⇒ x

_{i}

### − x

_{0}

### ./ c each element is a pair (value,{0, 1}), s.t “{0, 1}” means “{<, ≤}”

### Example:

### (0 ≤ x

1### ) ∧(0 < x

2### ) ∧(x

1### < 2) ∧(x

2### < 1) ∧(x

1### − x

2### ≥ 0)

(x0− x1≤ 0)### ∧(x

0− x2<0)### ∧(x

1### − x

0### < 2) ∧(x

2### − x

0### < 1) ∧(x

2− x1≤ 0)## Difference-bound matrices, DBMs (cont.)

### Use all-pairs shortest paths, check DBM

### idea: given x

_{i}

### − x

_{j}

### ./ c, x

_{i}

### − x

_{k}

### ./ c

_{1}

### and x

_{k}

### − x

_{j}

### ./ c

_{2}

### s.t.

### ./∈ {≤, <},

### then c is updated with c

_{1}

### + c

_{2}

### if c

_{1}

### + c

_{2}

### < c

### Satisfiable (no negative loops) =⇒ a non-empty clock zone Canonical: matrices with tightest possible constraints Canonical DBMs represent clock zones:

### equivalent sets of constraints ⇐⇒ same reduced DBM

59 / 101

## Canonical Data-structures for Zones: DBMs

## Complexity Issues

### In theory:

### Zone automaton might be exponentially bigger than the region automaton

### In practice:

### Fewer reachable vertices =⇒ performances much improved

61 / 101

## Timed Automata: summary

### Only continuous variables are timers

### Invariants and Guards: x ./ const, ./∈ {<, >, ≤, ≥}

### Actions: x:=0

### Reachability is decidable

### Clustering of regions into zones desirable in practice Tools: Uppaal, Kronos, RED ...

### Symbolic representation: matrices

## Decidable Problems with Timed Automata

### Model checking branching-time properties of timed automata Reachability in rectangular automata

### Timed bisimilarity: are two given timed automata bisimilar?

### Optimization: Compute shortest paths (e.g. minimum time reachability) in timed automata with costs on locations and edges Controller synthesis: Computing winning strategies in timed automata with controllable and uncontrollable transitions

63 / 101

## Outline

1

### Motivations

2

### Timed systems: Modeling and Semantics Timed automata

3

### Symbolic Reachability for Timed Systems Making the state space finite

### Region automata Zone automata

4

### Hybrid Systems: Modeling and Semantics Hybrid automata

5

6