Interval vs. Point Temporal Logic Model Checking: an Expressiveness Comparison

Interval vs. Point Temporal Logic Model Checking: an Expressiveness Comparison

Alberto Molinari

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

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

HS (state-based) semantics and model checking

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

• 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 prefix ρ^′ of ρ s.t. K , ρ^′|= ψ;

• K , ρ|= ⟨E⟩ ψ iff there is a suffix ρ^′ 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 , ρ |= ψ Possiblyinfinitely many tracks!

HS (state-based) semantics and model checking

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

• 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 prefix ρ^′ of ρ s.t. K , ρ^′|= ψ;

• K , ρ|= ⟨E⟩ ψ iff there is a suffix ρ^′ 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 , ρ |= ψ Possiblyinfinitely many tracks!

Branching (state-based) semantic var. of HS (HS

)

hBiϕ

ϕ

• Branching semantics of past/future operators [5]

Branching (state-based) semantic var. of HS (HS

) φ

⟨B⟩ φ

φ

⟨E⟩ φ

• Branching semantics of past/future operators [5]

Linear-past (computation-tree-based) semantic var. of HS (HS

)

• Similar toCTL+ linear past

• Thepast is linear, finite and cumulative[3, 4]

A computation tree

v0

{p, s} {q, s}^v1

v0

v1

v0 v1

v1 v0 v1

v1

v₀ v1 v₀ v1

· · ·

· · ·

Linear (trace-based) semantic var. of HS (HS

)

• Similar toLTL + PAST

• No branching in past/future

• K |=linψ, iff for each initial infinite path π and for each initial interval [0, i], it holds that IS_{K ,π}, [0, i]|= ψ

Expressiveness comparison

HS_lp HS_lin

HS_st

finitary CTL∗

LTL

CTL

≡ CTL∗

≡

<

̸=

<

̸=

̸=

̸=

̸=

Equivalence between LTL and HS

Equivalence between LTL and HS

FO formulasφ:

φ :=p∈ x | x = y | x < y | ¬ φ | φ ∧ φ | ∃x.φ .

Given a HS_linformula ψ⇝ ψFO=∃x((∀z.z ≥ x) ∧ ∀y.h(ψ, x, y))

h(p, x, y) =∀z.((z ≥ x ∧ z ≤ y) → p ∈ z), h(⟨E⟩ψ, x, y) = ∃z.(z > x ∧ z ≤ y ∧ h(ψ, z, y)), h(⟨B⟩ψ, x, y) = ∃z.(z ≥ x ∧ z < y ∧ h(ψ, x, z)), h(⟨E⟩ψ, x, y) = ∃z.(z < x ∧ h(ψ, z, y)), h(⟨B⟩ψ, x, y) = ∃z.(z > y ∧ h(ψ, x, z)).

Equivalence between LTL and HS

Theorem (Kamp’s Theorem [2])

Given a FO sentence φ over AP, one can construct an LTL formula ψ such that for all Kripke structures K over AP and infinite paths π,

π|= φ ⇐⇒ π, 0 |= ψ.

Theorem LTL≥ HSlin.

Equivalence between LTL and HS

Theorem (Kamp’s Theorem [2])

Given a FO sentence φ over AP, one can construct an LTL formula ψ such that for all Kripke structures K over AP and infinite paths π,

π|= φ ⇐⇒ π, 0 |= ψ.

Theorem LTL≥ HSlin.

Equivalence between LTL and HS

Conversely:

Theorem

Given an LTL formula φ, we can construct an AB formula ψ such that φin LTL is equivalent to ψ in AB_lin.

f(p) = p, f(Xψ) =⟨A⟩(length2∧ ⟨A⟩(length1∧ f(ψ))), f(ψ1Uψ2) =⟨A⟩(

⟨A⟩(length1∧ f(ψ2))∧ [B](⟨A⟩(length1∧ f(ψ1)) )

.

It holds that K |= ψ iff K |=linlength₁ → f(ψ) Corollary

HS_linand LTL have the same expressiveness.

A characterization of HS

A characterization of HS

• finitary CTL^∗≤ HSlp:

• BE and LTL define thesame finitary languages, as (a) BE⇝ LTL: Kamp’s th. over finite words

(b) LTL⇝ BE: LTL-closure [6]

• A to simulate∀/∃

• finitary CTL^∗≤ HSst

• HSlp≤ finitary CTL^∗(CTL^∗)

• viahybrid logics: hybrid-CTL^∗lp

A characterization of HS

• finitary CTL^∗≤ HSlp:

• BE and LTL define thesame finitary languages, as (a) BE⇝ LTL: Kamp’s th. over finite words

(b) LTL⇝ BE: LTL-closure [6]

• A to simulate∀/∃

• finitary CTL^∗≤ HSst

• HSlp≤ finitary CTL^∗(CTL^∗)

• viahybrid logics: hybrid-CTL^∗lp

Expressiveness comparison of HS

, HS

, HS

Expressiveness comparison of HS

, HS

, HS

• The reachability property∀G∃Fp is not LTL-expressible, but it is expressible in HS_lpand HS_st(by⟨B⟩ ⟨E⟩ p)

• but the LTL formula Fp cannot be expressed in HSlpor HSst

Expressiveness comparison of HS

, HS

, HS

Proposition

The LTL formula F p (equivalent to the CTL formula∀F p) cannot be expressed in either HS_lpor HSst.

Proof: We exhibit two families of Kripke structures (K_n)_n≥1and (Mn)_n≥1over{p} such that

• for all n≥ 1 the LTL formulaF p distinguishes K_nand M_n,

• but for every HSstformula ψ of size at most n, ψdoes not distinguish K_nand M_n.

Kn:

s0 s1 s2n t

... p

Expressiveness comparison of HS

, HS

, HS

Proposition

The LTL formula F p (equivalent to the CTL formula∀F p) cannot be expressed in either HS_lpor HSst.

Proof: We exhibit two families of Kripke structures (K_n)_n≥1and (Mn)_n≥1over{p} such that

• for all n≥ 1 the LTL formulaF p distinguishes K_nand M_n,

• but for every HSstformula ψ of size at most n, ψdoes not distinguish K_nand M_n.

M_n:

s0 s1 s2n t

... p

Expressiveness comparison of HS

, HS

, HS

• Already proved: CTL^∗≥ HSlp, HS_st≥ HSlp(=finitary CTL^∗)

• HS_lp, CTL, CTL^∗arenot sensitive to unravelling, HS_stis

• the CTL formula∀Fp cannot be expressed in HSlpor HS_st

• the (finitary) CTL^∗formula∃(

((p₁Up₂)∨ (q1Uq₂))U r)

cannot be expressed in CTL [1]

Expressiveness comparison of HS

, HS

, HS

• HS_lp, CTL, CTL^∗are not sensitive to unravelling.

K₁: p K₂: p p

“each state reachable from the initial one where p holds has a predecessor where p holds as well” can be expressed in HS_stby:

ψ =⟨E⟩(p ∧ length1)→ ⟨E⟩(length1∧ ⟨A⟩(p ∧ ¬length1)).

Corollary

HS_lp̸≥ HSst, hence HS_st >HS_lp.

References I

E. A. Emerson and J. Y. Halpern.

“Sometimes” and “not never” revisited: on branching versus linear time temporal logic.

Journal of the ACM, 33(1):151–178, 1986.

H. Kamp.

Tense Logic and the Theory of Linear Order.

PhD thesis, Ucla, 1968.

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

In ECAI, pages 543–548, 2014.

References II

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

Checking interval properties of computations.

Acta Informatica, 2016.

T. Wilke.

Classifying discrete temporal properties.

In STACS, LNCS 1563, pages 32–46, 1999.