• Non ci sono risultati.

# Model Checking Complex Systems against ITL Speciﬁcations with Regular Expressions

N/A
N/A
Protected

Condividi "Model Checking Complex Systems against ITL Speciﬁcations with Regular Expressions"

Copied!
41
0
0
Mostra di più ( pagine)

Testo completo

(1)

### Model Checking Complex Systems against ITL Speciﬁcations with Regular Expressions

Alberto Molinari

joint work with Laura Bozzelli, Angelo Montanari, and Adriano Peron Jan 20, 2017

University of Udine, Department of Mathematics, Computer Science, and Physics (DIMA)

(2)

### HS (state-based) semantics and model checking

Truth of a formula ψ over a track ρ of a Kripke structure K = (AP ,W, δ, µ, w0):

• K , ρ|= p iff p ∈

w∈states(ρ)µ(w), for any letter p∈ AP (homogeneity assumption) ;

• negation, disjunction, and conjunction are standard;

• K , ρ|= ⟨A⟩ ψ iff there is a track ρ s.t. lst(ρ) = fst(ρ)and K , ρ |= ψ;

• K , ρ|= ⟨B⟩ ψ iff there is a preﬁx ρ of ρ s.t. K , ρ|= ψ;

• K , ρ|= ⟨E⟩ ψ iff there is a sufﬁx ρ of ρ s.t. K , ρ|= ψ;

• the semantic clauses for⟨A⟩, ⟨B⟩, and ⟨E⟩ are similar Model Checking

K |= ψ ⇐⇒ for all initial tracks ρ of K , it holds that K , ρ |= ψ Possibly inﬁnitely many tracks!

(3)

### HS (state-based) semantics and model checking

Truth of a formula ψ over a track ρ of a Kripke structure K = (AP ,W, δ, µ, w0):

• K , ρ|= p iff p ∈

w∈states(ρ)µ(w), for any letter p∈ AP (homogeneity assumption) ;

• negation, disjunction, and conjunction are standard;

• K , ρ|= ⟨A⟩ ψ iff there is a track ρ s.t. lst(ρ) = fst(ρ)and K , ρ |= ψ;

• K , ρ|= ⟨B⟩ ψ iff there is a preﬁx ρ of ρ s.t. K , ρ|= ψ;

• K , ρ|= ⟨E⟩ ψ iff there is a sufﬁx ρ of ρ s.t. K , ρ|= ψ;

• the semantic clauses for⟨A⟩, ⟨B⟩, and ⟨E⟩ are similar Model Checking

K |= ψ ⇐⇒ for all initial tracks ρ of K , it holds that K , ρ |= ψ Possibly inﬁnitely many tracks!

(4)

### HS (state-based) semantics and model checking

Truth of a formula ψ over a track ρ of a Kripke structure K = (AP ,W, δ, µ, w0):

• K , ρ|= p iff p ∈ µ(fst(ρ), lst(ρ)), for any letter p ∈ AP (endpoint-based labeling) [1, 2];

• negation, disjunction, and conjunction are standard;

• K , ρ|= ⟨A⟩ ψ iff there is a track ρ s.t. lst(ρ) = fst(ρ)and K , ρ |= ψ;

• K , ρ|= ⟨B⟩ ψ iff there is a preﬁx ρ of ρ s.t. K , ρ|= ψ;

• K , ρ|= ⟨E⟩ ψ iff there is a sufﬁx ρ of ρ s.t. K , ρ|= ψ;

• the semantic clauses for⟨A⟩, ⟨B⟩, and ⟨E⟩ are similar Model Checking

K |= ψ ⇐⇒ for all initial tracks ρ of K , it holds that K , ρ |= ψ Possibly inﬁnitely many tracks!

(5)

### HS (state-based) semantics and model checking

Truth of a formula ψ over a track ρ of a Kripke structure K = (AP ,W, δ, µ, w0):

• K , ρ|= p other deﬁnitions?

• negation, disjunction, and conjunction are standard;

• K , ρ|= ⟨A⟩ ψ iff there is a track ρ s.t. lst(ρ) = fst(ρ)and K , ρ |= ψ;

• K , ρ|= ⟨B⟩ ψ iff there is a preﬁx ρ of ρ s.t. K , ρ|= ψ;

• K , ρ|= ⟨E⟩ ψ iff there is a sufﬁx ρ of ρ s.t. K , ρ|= ψ;

• the semantic clauses for⟨A⟩, ⟨B⟩, and ⟨E⟩ are similar Model Checking

K |= ψ ⇐⇒ for all initial tracks ρ of K , it holds that K , ρ |= ψ Possibly inﬁnitely many tracks!

(6)

### Example—Printer

v0

{p, pst} {p}v1 {p, pv2end}

Imagine we want to label theprocess of printinga single sheet of paper withp.

• Under homogeneity,

v0v1v2labeled by p⇒ v0v1and v1v2labeled by p

(7)

### Example—Printer

v0

{p, pst} {p}v1 {p, pv2end}

Imagine we want to label theprocess of printinga single sheet of paper withp.

• Under endpoint-based labeling, assuming p∈ µ(v0,v2), then (v0v1v2)nare all labeled by p

(8)

### (Usual) regular expressions

r ::= ε|a| r ∪ r | r · r | r for a∈ A.

Examples:

• r1=a· (b ∪ c)· b

• abb, acb, abccbb, …∈ L(r1)

• r2=

((a· b) ∪ (a · c))

• ε, ab, ac, acabac, …∈ L(r2)

• r3= ε· (a ∪ c)

• ε, a, ca, aac, …∈ L(r3)

(9)

### (Usual) regular expressions

r ::= ε|a| r ∪ r | r · r | r for a∈ A.

Examples:

• r1=a· (b ∪ c)· b

• abb, acb, abccbb, …∈ L(r1)

• r2= (

(a· b) ∪ (a · c))

• ε, ab, ac, acabac, …∈ L(r2)

• r3= ε· (a ∪ c)

• ε, a, ca, aac, …∈ L(r3)

(10)

### (Usual) regular expressions

r ::= ε|a| r ∪ r | r · r | r for a∈ A.

Examples:

• r1=a· (b ∪ c)· b

• abb, acb, abccbb, …∈ L(r1)

• r2= (

(a· b) ∪ (a · c))

• ε, ab, ac, acabac, …∈ L(r2)

• r3= ε· (a ∪ c)

• ε, a, ca, aac, …∈ L(r3)

(11)

### Our regular expressions

r ::= ε|ϕ| r ∪ r | r · r | r where ϕ is a Boolean (propositional) formula over AP.

v0

{p, s} {q, s}v1

• ρ = v0v1v0v1v1

• µ(ρ) ={p, s}{q, s}{p, s}{q, s}{q, s}

• ρ=v0v1v1v1v0

• µ(ρ) ={p, s}{q, s}{q, s}{q, s}{p, s}

Examples:

• r1= (p∧ s) · s· (p ∧ s)

• µ(ρ)̸∈ L(r1), but µ(ρ)∈ L(r1)

• r2= (¬p)

• µ(ρ)̸∈ L(r2), and µ(ρ)̸∈ L(r2)

(12)

### Nondeterministic ﬁnite automata (NFA)

r1=a· (b ∪ c)· b

q0

start q1 q2

Ar1

a

b, c

b

• abb, acb, abccbb, …∈ L(r1) =L(Ar1)

(13)

### Nondeterministic ﬁnite automata (NFA)

r1= (p∧ s) · s· (p ∧ s)

q0

start q1 q2

Ar1

(p∧ s) s

(p∧ s)

• µ(ρ) ={p, s}{q, s}{q, s}{q, s}{p, s} ∈ L(r1) =L(Ar1)

(14)

### HS semantics with regular expressions

Truth of a formula ψ over a track ρ of a Kripke structure K = (AP ,W, δ, µ, w0):

K , ρ|= r iff µ(ρ) ∈ L(r);

• negation, disjunction, and conjunction are standard;

• K , ρ|= ⟨A⟩ ψ iff there is a track ρ s.t. lst(ρ) = fst(ρ)and K , ρ |= ψ;

• K , ρ|= ⟨B⟩ ψ iff there is a preﬁx ρ of ρ s.t. K , ρ|= ψ;

• K , ρ|= ⟨E⟩ ψ iff there is a sufﬁx ρ of ρ s.t. K , ρ|= ψ;

• the semantic clauses for⟨A⟩, ⟨B⟩, and ⟨E⟩ are similar Model Checking

K |= ψ ⇐⇒ for all initial tracks ρ of K , it holds that K , ρ |= ψ Possibly inﬁnitely many tracks!

(15)

### HS semantics with regular expressions

Truth of a formula ψ over a track ρ of a Kripke structure K = (AP ,W, δ, µ, w0):

K , ρ|= r iff µ(ρ) ∈ L(r);

• negation, disjunction, and conjunction are standard;

• K , ρ|= ⟨A⟩ ψ iff there is a track ρ s.t. lst(ρ) = fst(ρ)and K , ρ |= ψ;

• K , ρ|= ⟨B⟩ ψ iff there is a preﬁx ρ of ρ s.t. K , ρ|= ψ;

• K , ρ|= ⟨E⟩ ψ iff there is a sufﬁx ρ of ρ s.t. K , ρ|= ψ;

• the semantic clauses for⟨A⟩, ⟨B⟩, and ⟨E⟩ are similar Model Checking

K |= ψ ⇐⇒ for all initial tracks ρ of K , it holds that K , ρ |= ψ

• To forcehomogeneity, all regular expressions inthe formula:

p· (p)

• forendpoint-basedlabeling, regular expressions in theformula:

(i,j)∈I

(qi· ⊤· qj)

for some I ⊆ {1, . . . , |W|}2, where qi∈ AP labelsonly wi∈ W.

Possibly inﬁnitely many tracks!

(16)

### HS semantics with regular expressions

Truth of a formula ψ over a track ρ of a Kripke structure K = (AP ,W, δ, µ, w0):

K , ρ|= r iff µ(ρ) ∈ L(r);

• negation, disjunction, and conjunction are standard;

• K , ρ|= ⟨A⟩ ψ iff there is a track ρ s.t. lst(ρ) = fst(ρ)and K , ρ |= ψ;

• K , ρ|= ⟨B⟩ ψ iff there is a preﬁx ρ of ρ s.t. K , ρ|= ψ;

• K , ρ|= ⟨E⟩ ψ iff there is a sufﬁx ρ of ρ s.t. K , ρ|= ψ;

• the semantic clauses for⟨A⟩, ⟨B⟩, and ⟨E⟩ are similar Model Checking

K |= ψ ⇐⇒ for all initial tracks ρ of K , it holds that K , ρ |= ψ Possibly inﬁnitely many tracks!

(17)

### HS semantics with regular expressions

Truth of a formula ψ over a track ρ of a Kripke structure K = (AP ,W, δ, µ, w0):

K , ρ|= r iff µ(ρ) ∈ L(r);

• negation, disjunction, and conjunction are standard;

• K , ρ|= ⟨A⟩ ψ iff there is a track ρ s.t. lst(ρ) = fst(ρ)and K , ρ |= ψ;

• K , ρ|= ⟨B⟩ ψ iff there is a preﬁx ρ of ρ s.t. K , ρ|= ψ;

• K , ρ|= ⟨E⟩ ψ iff there is a sufﬁx ρ of ρ s.t. K , ρ|= ψ;

• the semantic clauses for⟨A⟩, ⟨B⟩, and ⟨E⟩ are similar Model Checking

K |= ψ ⇐⇒ for all initial tracks ρ of K , it holds that K , ρ |= ψ Possiblyinﬁnitely many tracks!

(18)

### Decidability of MC for HS + regular expressions

Given K and an HS formula φ over AP, we build an NFA over K accepting the set of tracks ρ such that K , ρ|= φ.

Idea: for a regular expression r

v0

{p, s} {q, s}v1

q0 q1

q2

Ar1 (p

s)

s (p

s)

(19)

### Decidability of MC for HS + regular expressions

Given K and an HS formula φ over AP, we build an NFA over K accepting the set of tracks ρ such that K , ρ|= φ.

• for ψ = ψ1∧ ψ2, ψ = ψ1∨ ψ2: we do the usual constructions;

• for ψ =¬ψ: we complement the automaton (only the part for regular expressions);

• for ψ =⟨B⟩ ψ: we add asink ﬁnal statereachable from the “old” ﬁnal states;

• for ψ =⟨B⟩ ψ: we mark as ﬁnal all statesbackward reachable from the “old” ﬁnal states.

(20)

### Decidability of MC for HS + regular expressions

Given K and an HS formula φ over AP, we build an NFA over K accepting the set of tracks ρ such that K , ρ|= φ.

• for ψ = ψ1∧ ψ2, ψ = ψ1∨ ψ2: we do the usual constructions;

• for ψ =¬ψ: we complement the automaton (only the part for regular expressions);

• for ψ =⟨B⟩ ψ: we add asink ﬁnal statereachable from the “old”

ﬁnal states;

• for ψ =⟨B⟩ ψ: we mark as ﬁnal all statesbackward reachable from the “old” ﬁnal states.

(21)

### Decidability of MC for HS + regular expressions

Given K and an HS formula φ over AP, we build an NFA over K accepting the set of tracks ρ such that K , ρ|= φ.

• for ψ = ψ1∧ ψ2, ψ = ψ1∨ ψ2: we do the usual constructions;

• for ψ =¬ψ: we complement the automaton (only the part for regular expressions);

• for ψ =⟨B⟩ ψ: we add asink ﬁnal statereachable from the “old”

ﬁnal states;

Aψ :

• for ψ =⟨B⟩ ψ: we mark as ﬁnal all statesbackward reachable from the “old” ﬁnal states.

(22)

### Decidability of MC for HS + regular expressions

Given K and an HS formula φ over AP, we build an NFA over K accepting the set of tracks ρ such that K , ρ|= φ.

• for ψ = ψ1∧ ψ2, ψ = ψ1∨ ψ2: we do the usual constructions;

• for ψ =¬ψ: we complement the automaton (only the part for regular expressions);

• for ψ =⟨B⟩ ψ: we add asink ﬁnal statereachable from the “old”

ﬁnal states;

Aψ :

• for ψ =⟨B⟩ ψ: we mark as ﬁnal all statesbackward reachable from the “old” ﬁnal states.

(23)

### Decidability of MC for HS + regular expressions

Given K and an HS formula φ over AP, we build an NFA over K accepting the set of tracks ρ such that K , ρ|= φ.

• for ψ = ψ1∧ ψ2, ψ = ψ1∨ ψ2: we do the usual constructions;

• for ψ =¬ψ: we complement the automaton (only the part for regular expressions);

• for ψ =⟨B⟩ ψ: we add asink ﬁnal statereachable from the “old”

ﬁnal states;

• for ψ =⟨B⟩ ψ: we mark as ﬁnal all statesbackward reachable from the “old” ﬁnal states.

(24)

### Decidability of MC for HS + regular expressions

Given K and an HS formula φ over AP, we build an NFA over K accepting the set of tracks ρ such that K , ρ|= φ.

• for ψ = ψ1∧ ψ2, ψ = ψ1∨ ψ2: we do the usual constructions;

• for ψ =¬ψ: we complement the automaton (only the part for regular expressions);

• for ψ =⟨B⟩ ψ: we add asink ﬁnal statereachable from the “old”

ﬁnal states;

• for ψ =⟨B⟩ ψ: we mark as ﬁnal all statesbackward reachable from the “old” ﬁnal states.

Aψ :

(25)

### Decidability of MC for HS + regular expressions

Given K and an HS formula φ over AP, we build an NFA over K accepting the set of tracks ρ such that K , ρ|= φ.

• for ψ = ψ1∧ ψ2, ψ = ψ1∨ ψ2: we do the usual constructions;

• for ψ =¬ψ: we complement the automaton (only the part for regular expressions);

• for ψ =⟨B⟩ ψ: we add asink ﬁnal statereachable from the “old”

ﬁnal states;

• for ψ =⟨B⟩ ψ: we mark as ﬁnal all statesbackward reachable from the “old” ﬁnal states.

Aψ:

(26)

### The AABB fragment + regular expressions

We want to show that formulas of AABB + regular expressions can be checked by usingpolynomial working space.

To start with, we prove the following theorem, which is a building block of the PSPACE-model checking algorithm for AABB.

Theorem

Let ρ be a track of K and φ be an AABB formula with RE’s r1, . . . ,ru such that

K , ρ|= φ.

Then, there exists a track π of K such that

K , π|= φ and |π| ≤ |W| · (|φ| + 1) · 22uℓ=1|r|.

(27)

## π

1 2 3 4 5

1 2 3 4 5 6 7 8 9 10

π = ρ(1)ρ(4)ρ(5)ρ(7)ρ(10)

We want to guarantee that: for all π-positions j, with corresponding ρ-positions ij, and for all s = 1, . . . , u,As(µ(πj)) =As(µ(ρij))

Theorem (Exponential small-model for AABB)

Let ρ be a track of K and φ be an AABB formula with RE’s r1, . . . ,ru

such that K , ρ|= φ.

Then, there exists a track π of K ,induced by ρ, such that

K , π|= φ and |π| ≤ |W| · (|φ| + 1) · 22uℓ=1|r|.

(28)

## π

1 2 3 4 5

1 2 3 4 5 6 7 8 9 10

π = ρ(1)ρ(4)ρ(5)ρ(7)ρ(10)

We want to guarantee that: for all π-positions j, with corresponding ρ-positions ij, and for all s = 1, . . . , u,As(µ(πj)) =As(µ(ρij))

Theorem (Exponential small-model for AABB)

Let ρ be a track of K and φ be an AABB formula with RE’s r1, . . . ,ru

such that K , ρ|= φ.

Then, there exists a track π of K ,induced by ρ, such that

K , π|= φ and |π| ≤ |W| · (|φ| + 1) · 22uℓ=1|r|.

(29)

### Small model for AABB

Thesmall model is “strict”:

• Let pribe the i-th smallest prime.

It is well-known that pri∈ O(i log i).

• Let K = {p}v0

• Let us ﬁx some n∈ N. Theshortest tracksatisfying ψ =

n i=1

(ppri)

is ρ = vpr01···prn.

• The length of ψ is O(n· prn) =O(n2log n), but the length of ρ is pr1· · · prn≥ 2n.

(30)

### Small model for AABB

Thesmall model is “strict”:

• Let pribe the i-th smallest prime.

It is well-known that pri∈ O(i log i).

• Let K = {p}v0

• Let us ﬁx some n∈ N. Theshortest tracksatisfying ψ =

n i=1

(ppri)

is ρ = vpr01···prn.

• The length of ψ is O(n· prn) =O(n2log n), but the length of ρ is pr1· · · prn≥ 2n.

(31)

### Small model for AABB

Thesmall model is “strict”:

• Let pribe the i-th smallest prime.

It is well-known that pri∈ O(i log i).

• Let K = {p}v0

• Let us ﬁx some n∈ N. Theshortest tracksatisfying ψ =

n i=1

(ppri)

is ρ = vpr01···prn.

• The length of ψ is O(n· prn) =O(n2log n), but the length of ρ is pr1· · · prn≥ 2n.

(32)

### A PSPACE MC algorithm for AABB—Trials

• The algorithm can consider only tracks having length bounded by the exponential small model

• However,

they are stilltoo long!⇒triples (G, D(ψ), w) summarizing tracks, where

• G⊆ Subf⟨B⟩(ψ)contains thesubformulas that hold on some preﬁx

• D(ψ) is theconﬁguration of the DFAsafter reading the track,

• and w is the last state of the track Lemma

For all formulas ψ of BB, and for all tracks ρ, ρof K , if ρ and ρare summarized by the same triple (G, D(ψ), w), then

K , ρ|= ψ ⇐⇒ K , ρ|= ψ.

(33)

### A PSPACE MC algorithm for AABB—Trials

• The algorithm can consider only tracks having length bounded by the exponential small model

• However, they are stilltoo long!⇒triples (G, D(ψ), w) summarizing tracks, where

• G⊆ Subf⟨B⟩(ψ)contains thesubformulas that hold on some preﬁx

• D(ψ) is theconﬁguration of the DFAsafter reading the track,

• and w is the last state of the track Lemma

For all formulas ψ of BB, and for all tracks ρ, ρof K , if ρ and ρare summarized by the same triple (G, D(ψ), w), then

K , ρ|= ψ ⇐⇒ K , ρ|= ψ.

(34)

### A PSPACE MC algorithm for AABB—Trials

• The algorithm cannot explicitly store the DFAs for the regular expressions occurring in ψ ⇒ just store thecurrent statesof the computations of the DFAs and calculates on-the-ﬂy the

successor states

(35)

### A PSPACE MC algorithm for AABB

Algorithm 1 Check(K , ψ, w, G, D(ψ))

1: if ψ = r then r is a regular expression

2: if the current state of the DFA for r in advance(D(ψ), µ(w)) is ﬁnal then 3: return

4: else

5: return

6: else if ψ =¬ψor ψ = ψ1∧ ψ2then 7: Recursively

8: else if ψ =⟨B⟩ ψthen 9: return ψ∈ G 10: else if ψ =⟨B⟩ ψthen

11: for all b∈ {1, . . . , |W| · (2|ψ| + 1) · 22uℓ=1|r|− 1}, all (G,D(ψ),w)do 12: if Reach(K , ψ, (G, D(ψ), w), (G,D(ψ),w),b) and Check(K , ψ,w,G,D(ψ)) then 13: return

14: return

(36)

### A PSPACE MC algorithm for AABB

Algorithm 2 Check(K , ψ, w, G, D(ψ))

1: if ψ = r then r is a regular expression

2: if the current state of the DFA for r in advance(D(ψ), µ(w)) is ﬁnal then 3: return

4: else

5: return

6: else if ψ =¬ψor ψ = ψ1∧ ψ2then 7: Recursively

8: else if ψ =⟨B⟩ ψthen 9: return ψ∈ G 10: else if ψ =⟨B⟩ ψthen

11: for all b∈ {1, . . . , |W| · (2|ψ| + 1) · 22uℓ=1|r|− 1}, all (G,D(ψ),w)do 12: ifReach(K , ψ, (G, D(ψ), w), (G,D(ψ),w),b)and Check(K , ψ,w,G,D(ψ)) then 13: return

14: return

(37)

### AABB is PSPACE-complete

• We replace the sub-formulas⟨A⟩ ψ and ⟨A⟩ ψ with the regular expressions r⟨A⟩ ψand r⟨A⟩ ψ:

r⟨A⟩ ψ:=·( ∪

w∈W⟨A⟩ ψ

qw)

; r⟨A⟩ ψ:=( ∪

w∈W⟨A⟩ ψ

qw)

· ⊤.

• To determine W⟨A⟩ ψand W⟨A⟩ ψ, we iterate the previous algorithm Theorem

The MC problem for formulas of AABB over ﬁnite Kripke structures is PSPACE-complete.

Proof.

The purely propositional fragment of HS is hard for PSPACE: we prove this fact by a reduction from the PSPACE-complete universality problem for regular expressions.

(38)

### AABB is PSPACE-complete

• We replace the sub-formulas⟨A⟩ ψ and ⟨A⟩ ψ with the regular expressions r⟨A⟩ ψand r⟨A⟩ ψ:

r⟨A⟩ ψ:=·( ∪

w∈W⟨A⟩ ψ

qw)

; r⟨A⟩ ψ:=( ∪

w∈W⟨A⟩ ψ

qw)

· ⊤.

• To determine W⟨A⟩ ψand W⟨A⟩ ψ, we iterate the previous algorithm Theorem

The MC problem for formulas of AABB over ﬁnite Kripke structures is PSPACE-complete.

Proof.

The purely propositional fragment of HS is hard for PSPACE: we prove this fact by a reduction from the PSPACE-complete universality problem for regular expressions.

(39)

### Complexity results

Homogeneity Regular expressions

Full HS, BE non-elementary non-elementary EXPSPACE-hard EXPSPACE-hard

AABBE, AAEBE EXPSPACE non-elementary PSPACE-hard PSPACE-hard

AABE PSPACE-complete non-elementary PSPACE-hard AABB, BB, B,

PSPACE-complete PSPACE-complete AAEE, EE, E

AAB, AAE, AB, AE PNP-complete PSPACE-complete

AA, AB, AE, A, A PNP[O(log2n)]

PSPACE-complete PNP[O(log n)]-hard

Prop, B, E co-NP-complete PSPACE-complete

(40)

### Complexity results

Homogeneity Regular expressions

Full HS, BE non-elementary non-elementary EXPSPACE-hard EXPSPACE-hard

AABBE, AAEBE EXPSPACE non-elementary PSPACE-hard PSPACE-hard

AABE PSPACE-complete non-elementary PSPACE-hard AABB, BB, B,

PSPACE-complete PSPACE-complete AAEE, EE, E

AAB, AAE, AB, AE PNP-complete PSPACE-complete

AA, AB, AE, A, A PNP[O(log2n)]

PSPACE-complete PNP[O(log n)]-hard

(41)

### References

A. Lomuscio and J. Michaliszyn.

An epistemic Halpern-Shoham logic.

In IJCAI, pages 1010–1016, 2013.

A. Lomuscio and J. Michaliszyn.

Decidability of model checking multi-agent systems against a class of EHS speciﬁcations.

In ECAI, pages 543–548, 2014.

A. Lomuscio and J. Michaliszyn.

Model checking multi-agent systems against epistemic HS speciﬁcations with regular expressions.

In KR, pages 298–308, 2016.

A. Molinari, A. Montanari, A. Murano, G. Perelli, and A. Peron.

Checking interval properties of computations.

Acta Informatica, 2016.

Riferimenti

Documenti correlati

Photodegradation using semiconductor materials was found to be an effective Advanced Oxidation Process (AOP); the mechanism in water phase is widely studied using different types

Here, to make up for the relative sparseness of weather and hydrological data, or malfunctioning at the highest altitudes, we complemented ground data using series of remote sensing

Here we prove an exponential small-model property for the fragments AABB and AAEE, that is, if a trace ρ of a finite Kripke structure K satisfies a formula ϕ of AABB or AAEE, then

Esemplare al riguardo è il caso dell’Ipod dove tutti i pezzi, dalla scheda al microchip, sono fabbricati e assemblati nei paesi asiatici, ma il 60% del valore resta

Le aste OA e BC sono vincolate a terra attraverso due cerniere, mentre il disco incernierato nel punto D rotola senza strisciare sulla guida orizzontale,

Eppure, c’è un dubbio che interrompe lo sviluppo apparentemente lineare del ragionamento di Butler: distinguendo, all’interno della «riduzione totalizzante» operata

Negli ultimi anni l’attività di ricerca è pre- valentemente incentrata sull’uso delle tecnologie digitali per la valorizzazione del patrimonio culturale, anche in rela- zione

Nella seconda parte è stata puntata la lente sui tre grandi temi emersi durante il dibattito, il tema della guerra giusta, intesa come guerra legittima/legale, il tema della

Quando si verifica il boom economico in Italia, dalla fine degli anni ‘50 fino a istosamente anche nei luoghi tradizionali, Il cibo dei cavatori, sentito come cibo da

On 19 December 2018 the UN General Assembly approved the Global Compact for Safe, Orderly and Regular Migration (GCM), with 152 votes in favor, five against (Czech

Data are from the Italian national institute of statistics (ISTAT) which, recently, has made available national accounts consistent annual data for three kinds of labor inputs

Established in 2012 by GRNSPG and UNIPI, SILENCE Network connects Institutions and Organizations that are involved in the development and exploitation of thermal-hydraulic

The research analyzes, through surveying, the characteristics and significant components of the waterfront’s buildings: typological, functional distribution,

This result strongly suggests that we are observing discrete shifts from part-time to full-time work, as conjectured by Zabalza et al 1980 and Baker and Benjamin 1999, rather

In particular, generational accounting tries to determine the present value of the primary surplus that the future generation must pay to government in order to satisfy the

In particular, analysis of NGS data is classified as primary, secondary and tertiary (see Figure 3): primary analysis is essentially responsible of producing raw data;

Results show that WhatsApp is widely used in Hospital setting by nurses and physicians, and that an interplay exists between institutional and individual factors in determining

We performed a Principal Coordinate Analysis (PCoA) to detect possible differences in terms of taxonomic composition (Bray-Curtis distance) among diatom samples

If a process invokes the join() operation and does not leave the system for at least 3δ time units, or invokes the read() operation, or invokes the write () operation and does not

To this regard, we showed that the model checking technique can be suitable to perform planning and universal planning for continuous systems, by analysing the dynamics of a

Although it has been more than 20 years since the definition of two-stage linear model was given by

Using the spectra of Lyapunov maximum exponents constructed in accordance with the values of the control parameters α 1 and c of the system of FHN (1), it was shown that for such

Other forms of enforcement, on the other hand, lend themselves to almost complete automation, such as in the case of enforcement over (at least certain types of)

Seleziona la tua lingua

Il sito web verrà tradotto nella lingua selezionata.

Lingue suggerite per te:

Altre lingue: