Introduction to Formal Methods Chapter 11: Timed and Hybrid Systems

(1)

Introduction to Formal Methods Chapter 11: Timed and Hybrid Systems

Roberto Sebastiani

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

Teaching assistant:Enrico Magnago– enrico.magnago@unitn.it

CDLM in Informatica, academic year 2019-2020

last update: Sunday 24^thMay, 2020, 20:09

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, 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.

(2)

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

(3)

Motivations

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

(4)

Motivations

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

(5)

Motivations

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

(6)

Motivations

Hybrid Modeling

Hybrid machines = State machines + Dynamic Systems

(7)

Motivations

Hybrid Modeling: Examples

Automotive Applications

Vehicle Coordination Protocols Interacting Autonomous Robots

Bio-molecular Regulatory

Networks

(8)

Motivations

Hybrid Modeling: Examples

Automotive Applications Vehicle Coordination Protocols

Interacting Autonomous Robots

Bio-molecular Regulatory

Networks

(9)

Motivations

Hybrid Modeling: Examples

Automotive Applications Vehicle Coordination Protocols Interacting Autonomous Robots

Bio-molecular Regulatory

Networks

(10)

Motivations

Hybrid Modeling: Examples

Automotive Applications Vehicle Coordination Protocols Interacting Autonomous Robots

Bio-molecular Regulatory

Networks

(11)

Timed systems: Modeling and Semantics

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

(12)

Timed systems: Modeling and Semantics Timed automata

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

(13)

Timed Automata

(14)

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;

(15)

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

(16)

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

(17)

Timed Automata

Locations l

₁

, l

₂

, ... (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

(18)

Timed Automata

Locations l

₁

, l

₂

, ... (like in standard automata)

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

Clocks : x, y,... ∈ Q

⁺

Guards : (x ./ C) s.t. ./ ∈ {≤, <, ≥, >}, C ∈ N

Resets (x := 0)

Invariants: (x ./ C) s.t. ./ ∈ {≤, <, ≥, >}, C ∈ N

(x ≥ 4) (y ≤ 2) a

y := 0 l1

l2

(19)

Timed Automata

Locations l

₁

, l

₂

, ... (like in standard automata)

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

Clocks: x, y,... ∈ Q

⁺

Guards: (x ./ C) s.t. ./ ∈ {≤, <, ≥, >}, C ∈ N

Resets (x := 0)

Invariants : (x ./ C) s.t. ./ ∈ {≤, <, ≥, >}, C ∈ N

(x ≥ 4) (y ≤ 2) a

y := 0 l1

(x ≤ 5)

l2

(x > 4) (y ≤ 3)

(20)

Timed Automata: States and Transitions

State: hl

_i

, x

₁

, x

₂

i

hl₁,4, 7i:

OK!

hl₂,2, 4i:

not OK!(violates invariant in l2)

Switch: hl

_i

, x , y i −→ hl

^a _j

, x

⁰

, y

⁰

i

hl₁,4.5, 2i−→ hl^a ₂,4.5, 0i:

OK!

hl₁,6, 2i−→ hl^a ₂,6, 0i:

not OK!(violates invar. in l1)

hl₁,3, 2i−→ hl^a ₂,3, 0i:

not OK!(violates guard)

hl₁,4.5, 2i−→ hl^a ₂,4.5, 2i:

not OK!(violates reset)

hl₁,4, 2i−→ hl^a ₂,4, 0i:

not OK!(violates invar. in l₂)

Wait (time elapse): hl

_i

, x , y i −→ hl

^δ _i

, x + δ, y + δi

hl₁,3, 0i−→ hl² ₁,5, 2i:

OK!

hl₁,3, 0i−→ hl³ ₁,6, 3i:

(x1≥ 4) (x2≤ 2) a

y := 0

L1

(x1≤ 5)

L2

(x1>4) (x2≤ 3)

(21)

Timed Automata: States and Transitions

State: hl

_i

, x

₁

, x

₂

i

hl₁,4, 7i:

OK! hl₂,2, 4i:

Switch: hl

_i

, x , y i −→ hl

^a _j

, x

⁰

, y

⁰

i

hl₁,4.5, 2i−→ hl^a ₂,4.5, 0i:

OK!

hl₁,6, 2i−→ hl^a ₂,6, 0i:

hl₁,3, 2i−→ hl^a ₂,3, 0i:

hl₁,4.5, 2i−→ hl^a ₂,4.5, 2i:

hl₁,4, 2i−→ hl^a ₂,4, 0i:

Wait (time elapse): hl

_i

, x , y i −→ hl

^δ _i

, x + δ, y + δi

hl₁,3, 0i−→ hl² ₁,5, 2i:

OK!

hl₁,3, 0i−→ hl³ ₁,6, 3i:

(x1≥ 4) (x2≤ 2) a

y := 0

L1

(x1≤ 5)

L2

(x1>4) (x2≤ 3)

(22)

Timed Automata: States and Transitions

State: hl

_i

, x

₁

, x

₂

i

hl₁,4, 7i: OK!

hl₂,2, 4i:

Switch: hl

_i

, x , y i −→ hl

^a _j

, x

⁰

, y

⁰

i

hl₁,4.5, 2i−→ hl^a ₂,4.5, 0i:

OK!

hl₁,6, 2i−→ hl^a ₂,6, 0i:

hl₁,3, 2i−→ hl^a ₂,3, 0i:

hl₁,4.5, 2i−→ hl^a ₂,4.5, 2i:

hl₁,4, 2i−→ hl^a ₂,4, 0i:

Wait (time elapse): hl

_i

, x , y i −→ hl

^δ _i

, x + δ, y + δi

hl₁,3, 0i−→ hl² ₁,5, 2i:

OK!

hl₁,3, 0i−→ hl³ ₁,6, 3i:

(x1≥ 4) (x2≤ 2) a

y := 0

L1

(x1≤ 5)

L2

(x1>4) (x2≤ 3)

(23)

Timed Automata: States and Transitions

State: hl

_i

, x

₁

, x

₂

i

hl₁,4, 7i: OK!

hl₂,2, 4i:

Switch: hl

_i

, x , y i −→ hl

^a _j

, x

⁰

, y

⁰

i

hl₁,4.5, 2i−→ hl^a ₂,4.5, 0i:

OK!

hl₁,6, 2i−→ hl^a ₂,6, 0i:

hl₁,3, 2i−→ hl^a ₂,3, 0i:

hl₁,4.5, 2i−→ hl^a ₂,4.5, 2i:

hl₁,4, 2i−→ hl^a ₂,4, 0i:

Wait (time elapse): hl

_i

, x , y i −→ hl

^δ _i

, x + δ, y + δi

hl₁,3, 0i−→ hl² ₁,5, 2i:

OK!

hl₁,3, 0i−→ hl³ ₁,6, 3i:

(x1≥ 4) (x2≤ 2) a

y := 0

L1

(x1≤ 5)

L2

(x1>4) (x2≤ 3)

(24)

Timed Automata: States and Transitions

State: hl

_i

, x

₁

, x

₂

i

hl₁,4, 7i: OK!

hl₂,2, 4i:not OK!(violates invariant in l2)

Switch: hl

_i

, x , y i −→ hl

^a _j

, x

⁰

, y

⁰

i

hl₁,4.5, 2i−→ hl^a ₂,4.5, 0i:

OK!

hl₁,6, 2i−→ hl^a ₂,6, 0i:

hl₁,3, 2i−→ hl^a ₂,3, 0i:

hl₁,4.5, 2i−→ hl^a ₂,4.5, 2i:

hl₁,4, 2i−→ hl^a ₂,4, 0i:

Wait (time elapse): hl

_i

, x , y i −→ hl

^δ _i

, x + δ, y + δi

hl₁,3, 0i−→ hl² ₁,5, 2i:

OK!

hl₁,3, 0i−→ hl³ ₁,6, 3i:

(x1≥ 4) (x2≤ 2) a

y := 0

L1

(x1≤ 5)

L2

(x1>4) (x2≤ 3)

(25)

Timed Automata: States and Transitions

State: hl

_i

, x

₁

, x

₂

i

hl₁,4, 7i: OK!

Switch: hl

_i

, x , y i −→ hl

^a _j

, x

⁰

, y

⁰

i

hl₁,4.5, 2i−→ hl^a ₂,4.5, 0i:

OK!

hl₁,6, 2i−→ hl^a ₂,6, 0i:

hl₁,3, 2i−→ hl^a ₂,3, 0i:

hl₁,4.5, 2i−→ hl^a ₂,4.5, 2i:

hl₁,4, 2i−→ hl^a ₂,4, 0i:

Wait (time elapse): hl

_i

, x , y i −→ hl

^δ _i

, x + δ, y + δi

hl₁,3, 0i−→ hl² ₁,5, 2i:

OK!

hl₁,3, 0i−→ hl³ ₁,6, 3i:

(x1≥ 4) (x2≤ 2) a

y := 0

L1

(x1≤ 5)

L2

(x1>4) (x2≤ 3)

(26)

Timed Automata: States and Transitions

State: hl

_i

, x

₁

, x

₂

i

hl₁,4, 7i: OK!

Switch: hl

_i

, x , y i −→ hl

^a _j

, x

⁰

, y

⁰

i

hl₁,4.5, 2i−→ hl^a ₂,4.5, 0i:

OK! hl₁,6, 2i−→ hl^a ₂,6, 0i:

hl₁,3, 2i−→ hl^a ₂,3, 0i:

hl₁,4.5, 2i−→ hl^a ₂,4.5, 2i:

hl₁,4, 2i−→ hl^a ₂,4, 0i:

Wait (time elapse): hl

_i

, x , y i −→ hl

^δ _i

, x + δ, y + δi

hl₁,3, 0i−→ hl² ₁,5, 2i:

OK!

hl₁,3, 0i−→ hl³ ₁,6, 3i:

(x1≥ 4) (x2≤ 2) a

y := 0

L1

(x1≤ 5)

L2

(x1>4) (x2≤ 3)

(27)

Timed Automata: States and Transitions

State: hl

_i

, x

₁

, x

₂

i

hl₁,4, 7i: OK!

Switch: hl

_i

, x , y i −→ hl

^a _j

, x

⁰

, y

⁰

i

hl₁,4.5, 2i−→ hl^a ₂,4.5, 0i: OK!

hl₁,6, 2i−→ hl^a ₂,6, 0i:

hl₁,3, 2i−→ hl^a ₂,3, 0i:

hl₁,4.5, 2i−→ hl^a ₂,4.5, 2i:

hl₁,4, 2i−→ hl^a ₂,4, 0i:

Wait (time elapse): hl

_i

, x , y i −→ hl

^δ _i

, x + δ, y + δi

hl₁,3, 0i−→ hl² ₁,5, 2i:

OK!

hl₁,3, 0i−→ hl³ ₁,6, 3i:

(x1≥ 4) (x2≤ 2) a

y := 0

L1

(x1≤ 5)

L2

(x1>4) (x2≤ 3)

(28)

Timed Automata: States and Transitions

State: hl

_i

, x

₁

, x

₂

i

hl₁,4, 7i: OK!

Switch: hl

_i

, x , y i −→ hl

^a _j

, x

⁰

, y

⁰

i

hl₁,4.5, 2i−→ hl^a ₂,4.5, 0i: OK!

hl₁,6, 2i−→ hl^a ₂,6, 0i:

not OK!(violates invar. in l1) hl₁,3, 2i−→ hl^a ₂,3, 0i:

hl₁,4.5, 2i−→ hl^a ₂,4.5, 2i:

hl₁,4, 2i−→ hl^a ₂,4, 0i:

Wait (time elapse): hl

_i

, x , y i −→ hl

^δ _i

, x + δ, y + δi

hl₁,3, 0i−→ hl² ₁,5, 2i:

OK!

hl₁,3, 0i−→ hl³ ₁,6, 3i:

(x1≥ 4) (x2≤ 2) a

y := 0

L1

(x1≤ 5)

L2

(x1>4) (x2≤ 3)

(29)

Timed Automata: States and Transitions

State: hl

_i

, x

₁

, x

₂

i

hl₁,4, 7i: OK!

Switch: hl

_i

, x , y i −→ hl

^a _j

, x

⁰

, y

⁰

i

hl₁,4.5, 2i−→ hl^a ₂,4.5, 0i: OK!

hl₁,6, 2i−→ hl^a ₂,6, 0i:not OK!(violates invar. in l1)

hl₁,3, 2i−→ hl^a ₂,3, 0i:

hl₁,4.5, 2i−→ hl^a ₂,4.5, 2i:

hl₁,4, 2i−→ hl^a ₂,4, 0i:

Wait (time elapse): hl

_i

, x , y i −→ hl

^δ _i

, x + δ, y + δi

hl₁,3, 0i−→ hl² ₁,5, 2i:

OK!

hl₁,3, 0i−→ hl³ ₁,6, 3i:

(x1≥ 4) (x2≤ 2) a

y := 0

L1

(x1≤ 5)

L2

(x1>4) (x2≤ 3)

(30)

Timed Automata: States and Transitions

State: hl

_i

, x

₁

, x

₂

i

hl₁,4, 7i: OK!

Switch: hl

_i

, x , y i −→ hl

^a _j

, x

⁰

, y

⁰

i

hl₁,4.5, 2i−→ hl^a ₂,4.5, 0i: OK!

hl₁,6, 2i−→ hl^a ₂,6, 0i:not OK!(violates invar. in l1) hl₁,3, 2i−→ hl^a ₂,3, 0i:

not OK!(violates guard) hl₁,4.5, 2i−→ hl^a ₂,4.5, 2i:

hl₁,4, 2i−→ hl^a ₂,4, 0i:

Wait (time elapse): hl

_i

, x , y i −→ hl

^δ _i

, x + δ, y + δi

hl₁,3, 0i−→ hl² ₁,5, 2i:

OK!

hl₁,3, 0i−→ hl³ ₁,6, 3i:

(x1≥ 4) (x2≤ 2) a

y := 0

L1

(x1≤ 5)

L2

(x1>4) (x2≤ 3)

(31)

Timed Automata: States and Transitions

State: hl

_i

, x

₁

, x

₂

i

hl₁,4, 7i: OK!

Switch: hl

_i

, x , y i −→ hl

^a _j

, x

⁰

, y

⁰

i

hl₁,4.5, 2i−→ hl^a ₂,4.5, 0i: OK!

hl₁,6, 2i−→ hl^a ₂,6, 0i:not OK!(violates invar. in l1) hl₁,3, 2i−→ hl^a ₂,3, 0i:not OK!(violates guard)

hl₁,4.5, 2i−→ hl^a ₂,4.5, 2i:

hl₁,4, 2i−→ hl^a ₂,4, 0i:

Wait (time elapse): hl

_i

, x , y i −→ hl

^δ _i

, x + δ, y + δi

hl₁,3, 0i−→ hl² ₁,5, 2i:

OK!

hl₁,3, 0i−→ hl³ ₁,6, 3i:

(x1≥ 4) (x2≤ 2) a

y := 0

L1

(x1≤ 5)

L2

(x1>4) (x2≤ 3)

(32)

Timed Automata: States and Transitions

State: hl

_i

, x

₁

, x

₂

i

hl₁,4, 7i: OK!

Switch: hl

_i

, x , y i −→ hl

^a _j

, x

⁰

, y

⁰

i

hl₁,4.5, 2i−→ hl^a ₂,4.5, 0i: OK!

hl₁,6, 2i−→ hlâ ₂,6, 0i:not OK!(violates invar. in l1) hl₁,3, 2i−→ hlâ ₂,3, 0i:not OK!(violates guard) hl₁,4.5, 2i−→ hlâ ₂,4.5, 2i:

not OK!(violates reset) hl₁,4, 2i−→ hl^a ₂,4, 0i:

Wait (time elapse): hl

_i

, x , y i −→ hl

^δ _i

, x + δ, y + δi

hl₁,3, 0i−→ hl² ₁,5, 2i:

OK!

hl₁,3, 0i−→ hl³ ₁,6, 3i:

(x1≥ 4) (x2≤ 2) a

y := 0

L1

(x1≤ 5)

L2

(x1>4) (x2≤ 3)

(33)

Timed Automata: States and Transitions

State: hl

_i

, x

₁

, x

₂

i

hl₁,4, 7i: OK!

Switch: hl

_i

, x , y i −→ hl

^a _j

, x

⁰

, y

⁰

i

hl₁,4.5, 2i−→ hl^a ₂,4.5, 0i: OK!

hl₁,6, 2i−→ hlâ ₂,6, 0i:not OK!(violates invar. in l1) hl₁,3, 2i−→ hlâ ₂,3, 0i:not OK!(violates guard) hl₁,4.5, 2i−→ hlâ ₂,4.5, 2i:not OK!(violates reset)

hl₁,4, 2i−→ hl^a ₂,4, 0i:

Wait (time elapse): hl

_i

, x , y i −→ hl

^δ _i

, x + δ, y + δi

hl₁,3, 0i−→ hl² ₁,5, 2i:

OK!

hl₁,3, 0i−→ hl³ ₁,6, 3i:

(x1≥ 4) (x2≤ 2) a

y := 0

L1

(x1≤ 5)

L2

(x1>4) (x2≤ 3)

(34)

Timed Automata: States and Transitions

State: hl

_i

, x

₁

, x

₂

i

hl₁,4, 7i: OK!

Switch: hl

_i

, x , y i −→ hl

^a _j

, x

⁰

, y

⁰

i

hl₁,4.5, 2i−→ hl^a ₂,4.5, 0i: OK!

hl₁,6, 2i−→ hlâ ₂,6, 0i:not OK!(violates invar. in l1) hl₁,3, 2i−→ hlâ ₂,3, 0i:not OK!(violates guard) hl₁,4.5, 2i−→ hlâ ₂,4.5, 2i:not OK!(violates reset) hl₁,4, 2i−→ hlâ ₂,4, 0i:

Wait (time elapse): hl

_i

, x , y i −→ hl

^δ _i

, x + δ, y + δi

hl₁,3, 0i−→ hl² ₁,5, 2i:

OK!

hl₁,3, 0i−→ hl³ ₁,6, 3i:

(x1≥ 4) (x2≤ 2) a

y := 0

L1

(x1≤ 5)

L2

(x1>4) (x2≤ 3)

(35)

Timed Automata: States and Transitions

State: hl

_i

, x

₁

, x

₂

i

hl₁,4, 7i: OK!

Switch: hl

_i

, x , y i −→ hl

^a _j

, x

⁰

, y

⁰

i

hl₁,4.5, 2i−→ hl^a ₂,4.5, 0i: OK!

hl₁,6, 2i−→ hlâ ₂,6, 0i:not OK!(violates invar. in l1) hl₁,3, 2i−→ hlâ ₂,3, 0i:not OK!(violates guard) hl₁,4.5, 2i−→ hlâ ₂,4.5, 2i:not OK!(violates reset) hl₁,4, 2i−→ hlâ ₂,4, 0i:not OK!(violates invar. in l₂)

Wait (time elapse): hl

_i

, x , y i −→ hl

^δ _i

, x + δ, y + δi

hl₁,3, 0i−→ hl² ₁,5, 2i:

OK!

hl₁,3, 0i−→ hl³ ₁,6, 3i:

(x1≥ 4) (x2≤ 2) a

y := 0

L1

(x1≤ 5)

L2

(x1>4) (x2≤ 3)

(36)

Timed Automata: States and Transitions

State: hl

_i

, x

₁

, x

₂

i

hl₁,4, 7i: OK!

Switch: hl

_i

, x , y i −→ hl

^a _j

, x

⁰

, y

⁰

i

hl₁,4.5, 2i−→ hl^a ₂,4.5, 0i: OK!

Wait (time elapse): hl

_i

, x , y i −→ hl

^δ _i

, x + δ, y + δi

hl₁,3, 0i−→ hl² ₁,5, 2i:

OK!

hl₁,3, 0i−→ hl³ ₁,6, 3i:

(x1≥ 4) (x2≤ 2) a

y := 0

L1

(x1≤ 5)

L2

(x1>4) (x2≤ 3)

(37)

Timed Automata: States and Transitions

State: hl

_i

, x

₁

, x

₂

i

hl₁,4, 7i: OK!

Switch: hl

_i

, x , y i −→ hl

^a _j

, x

⁰

, y

⁰

i

hl₁,4.5, 2i−→ hl^a ₂,4.5, 0i: OK!

Wait (time elapse): hl

_i

, x , y i −→ hl

^δ _i

, x + δ, y + δi

hl₁,3, 0i−→ hl² ₁,5, 2i:

OK! hl₁,3, 0i−→ hl³ ₁,6, 3i:

(x1≥ 4) (x2≤ 2) a

y := 0

L1

(x1≤ 5)

L2

(x1>4) (x2≤ 3)

(38)

Timed Automata: States and Transitions

State: hl

_i

, x

₁

, x

₂

i

hl₁,4, 7i: OK!

Switch: hl

_i

, x , y i −→ hl

^a _j

, x

⁰

, y

⁰

i

hl₁,4.5, 2i−→ hl^a ₂,4.5, 0i: OK!

Wait (time elapse): hl

_i

, x , y i −→ hl

^δ _i

, x + δ, y + δi

hl₁,3, 0i−→ hl² ₁,5, 2i: OK!

hl₁,3, 0i−→ hl³ ₁,6, 3i:

(x1≥ 4) (x2≤ 2) a

y := 0

L1

(x1≤ 5)

L2

(x1>4) (x2≤ 3)

(39)

Timed Automata: States and Transitions

State: hl

_i

, x

₁

, x

₂

i

hl₁,4, 7i: OK!

Switch: hl

_i

, x , y i −→ hl

^a _j

, x

⁰

, y

⁰

i

hl₁,4.5, 2i−→ hl^a ₂,4.5, 0i: OK!

Wait (time elapse): hl

_i

, x , y i −→ hl

^δ _i

, x + δ, y + δi

hl₁,3, 0i−→ hl² ₁,5, 2i: OK!

hl₁,3, 0i−→ hl³ ₁,6, 3i:

(x1≥ 4) (x2≤ 2) a

y := 0

L1

(x1≤ 5)

L2

(x1>4) (x2≤ 3)

(40)

Timed Automata: States and Transitions

State: hl

_i

, x

₁

, x

₂

i

hl₁,4, 7i: OK!

Switch: hl

_i

, x , y i −→ hl

^a _j

, x

⁰

, y

⁰

i

hl₁,4.5, 2i−→ hl^a ₂,4.5, 0i: OK!

Wait (time elapse): hl

_i

, x , y i −→ hl

^δ _i

, x + δ, y + δi

hl₁,3, 0i−→ hl² ₁,5, 2i: OK!

hl₁,3, 0i−→ hl³ ₁,6, 3i:not OK!(violates invar. in l1)

(x1≥ 4) (x2≤ 2) a

y := 0

L1

(x1≤ 5)

L2

(x1>4) (x2≤ 3)

(41)

Timed Automata: Formal Syntax

Timed Automaton hL, L

⁰

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

L

⁰

⊆ 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

⁰

i s.t.

l: source location a: label

ϕ: clock constraints λ⊆ X : clocks to be reset l⁰: target location

(x1≥ 4) (x2≤ 2) a

y := 0

L1

(x1≤ 5)

L2

(x1>4) (x2≤ 3)

(42)

Timed Automata: Formal Syntax

Timed Automaton hL, L

⁰

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

L

⁰

⊆ 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

⁰

i s.t.

(x1≥ 4) (x2≤ 2) a

y := 0

L1

(x1≤ 5)

L2

(x1>4) (x2≤ 3)

(43)

Timed Automata: Formal Syntax

Timed Automaton hL, L

⁰

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

L

⁰

⊆ 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

⁰

i s.t.

(x1≥ 4) (x2≤ 2) a

y := 0

L1

(x1≤ 5)

L2

(x1>4) (x2≤ 3)

(44)

Timed Automata: Formal Syntax

Timed Automaton hL, L

⁰

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

L

⁰

⊆ 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

⁰

i s.t.

(x1≥ 4) (x2≤ 2) a

y := 0

L1

(x1≤ 5)

L2

(x1>4) (x2≤ 3)

(45)

Timed Automata: Formal Syntax

Timed Automaton hL, L

⁰

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

L

⁰

⊆ 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

⁰

i s.t.

(x1≥ 4) (x2≤ 2) a

y := 0

L1

(x1≤ 5)

L2

(x1>4) (x2≤ 3)

(46)

Timed Automata: Formal Syntax

Timed Automaton hL, L

⁰

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

L

⁰

⊆ 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

⁰

i s.t.

(x1≥ 4) (x2≤ 2) a

y := 0

L1

(x1≤ 5)

L2

(x1>4) (x2≤ 3)

(47)

Timed Automata: Formal Syntax

Timed Automaton hL, L

⁰

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

L

⁰

⊆ 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

⁰

i s.t.

l: source location

a: label

(x1≥ 4) (x2≤ 2) a

y := 0

L1

(x1≤ 5)

L2

(x1>4) (x2≤ 3)

(48)

Timed Automata: Formal Syntax

Timed Automaton hL, L

⁰

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

L

⁰

⊆ 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

⁰

i s.t.

(x1≥ 4) (x2≤ 2) a

y := 0

L1

(x1≤ 5)

L2

(x1>4) (x2≤ 3)

(49)

Timed Automata: Formal Syntax

Timed Automaton hL, L

⁰

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

L

⁰

⊆ 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

⁰

i s.t.

ϕ: clock constraints

λ⊆ X : clocks to be reset l⁰: target location

(x1≥ 4) (x2≤ 2) a

y := 0

L1

(x1≤ 5)

L2

(x1>4) (x2≤ 3)

(50)

Timed Automata: Formal Syntax

Timed Automaton hL, L

⁰

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

L

⁰

⊆ 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

⁰

i s.t.

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

l⁰: target location

(x1≥ 4) (x2≤ 2) a

y := 0

L1

(x1≤ 5)

L2

(x1>4) (x2≤ 3)

(51)

Timed Automata: Formal Syntax

Timed Automaton hL, L

⁰

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

L

⁰

⊆ 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

⁰

i s.t.

(x1≥ 4) (x2≤ 2) a

y := 0

L1

(x1≤ 5)

L2

(x1>4) (x2≤ 3)

(52)

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

(x1≥ 4) (x2≤ 2) a

y := 0

L₁

(x1≤ 5)

L2

(x1>4) (x2≤ 3)

(53)

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

(x1≥ 4) (x2≤ 2) a

y := 0

L₁

(x1≤ 5)

L2

(x1>4) (x2≤ 3)