A Guided Tour through Interval Temporal Logics Lecture 3: Languages and expressiveness.

(1)

Lecture 3: Languages and expressiveness.

Angelo Montanari

Department of Mathematics and Computer Science, University of Udine, Italy

angelo.montanari@uniud.it

Gargnano, August 20-25, 2012

(2)

• Comparing the expressiveness of fragments of HS

(bisimulation and bisimulation games on interval structures)

• A complete classification of the expressiveness of HS fragments on the class of all linear orders

• Standard translations for interval temporal logics

• Expressive completeness results

(3)

A modal operator hX i of HS is definablein an HS-fragment F, denoted hX i F, if hX ip ≡ ψ for some formula ψ = ψ(p) ∈ F, for any fixed propositional variable p.

In such a case, the equivalence hX ip ≡ ψ is called an inter-definability equation for hX i in F.

Notation.

For each modal operator hX i, we denote by R_X the corresponding Allen’s relation.

With every subset X = {hX1i, . . . , hXki} of HS modalities we associate the fragment FX of HS, denoted X₁X₂. . .X_k, with formulas only featuring modalities from X .

As an example, BB denotes the fragment involving the modalities hBi and hBi only.

(4)

To show undefinability of a given modality in a certain interval logic, one can use bisimulation and invariance of modal formulas with respect to bisimulations.

Let F be the considered interval logic. An F-bisimulation between two interval models M = hI(D), V i and M^′= hI(D^′), V^′i over the set of proposition letters AP is a relation Z ⊆ I(D) × I(D^′) satisfying the following properties:

• local condition: pairs of Z -related intervals satisfy the same proposition letters over AP

• forward condition: if ([i , j], [i^′, j^′]) ∈ Z and ([i , j], [h, k]) ∈ RX

for some hX i ∈ F, then there exists [h^′, k^′] such that ([i^′, j^′], [h^′, k^′]) ∈ R_X and ([h, k], [h^′, k^′]) ∈ Z

(5)

• backward condition: if ([i , j], [i^′, j^′]) ∈ Z and

([i^′, j^′], [h^′, k^′]) ∈ R_X for some hX i ∈ F, then there exists [h, k] such that ([i , j], [h, k]) ∈ R_X and ([h, k], [h^′, k^′]) ∈ Z . Since any F-bisimulation preserves the truth of all formulas in F, to prove that an operator hX i is not definable in F,

it suffices to construct a pair of interval models M and M^′ and an F-bisimulation between them such that

M,[i , j] hX ip and M^′,[i^′, j^′] 6 hX ip,

for a pair of F-bisimilar intervals [i , j] ∈ M and [i^′, j^′] ∈ M^′.

(6)

Proof. Let us consider the pair of interval models M = hI (N), V i and M^′ = hI⁻(N), V^′i, over the set of proposition letters

AP = {p}, where V (p) = V^′(p) = {[i , i + 1] : i ≥ 0}. Moreover, let Z ⊆ I⁻(N) × I⁻(N) be the set

{([i , j], [i , j]) : 0 ≤ i < j} ∪ {([i , j], [i + 1, j + 1]) : 0 ≤ i < j}

(Part of) the relation Z can be depicted as follows:

0 1 2 3 4 5

. . .

p p p p p

(7)

Z is anA-bisimulation.

Checking that it satisfies the local conditionis immediate.

As for the forward condition, we must distinguish two cases.

First, we must consider any pair of the form ([i , j], [i , j]). In such a case, the hAi-move from [i , j] to [j, k] in M can be simulated by the very same hAi-move from [i , j] to [j, k] in M^′. Notice that p-intervals come into play when j = i + 1 or k = j + 1 (or both).

The second case is that of pairs of the form ([i , j], [i + 1, j + 1]). In such a case, the hAi-move from [i , j] to [j, k] in M can be

simulated by the hAi-move from [i + 1, j + 1] to [j + 1, k + 1] in M^′. As in the previous case, p-intervals come into play when j = i + 1 or k = j + 1 (or both).

Satisfaction of the backward condition can be checked in a very similar way.

(8)

the relation induced by the modality hLi. To this end, consider the pair ([1, 2], [2, 3]) ∈ Z .

We have that M^′,[2, 3] |= hLip, while M, [1, 2] 6|= hLip.

Corollary. The modality hAi is not definable in A over N.

Proof. As the modal operator hLi is definable in any interval logic featuring the modal operator hAi (for any fixed proposition letter p, it holds that hLip ≡ hAihAip), the thesis immediately follows from the above theorem.

It is worth pointing out that the bisimulation exploited in the proof of the above theorem still works if we replace N by Z, Q, or R.

Exercise. To show that the modality hAi is not definable in AL over N.

(9)

(10)

Existence of bisimulation between two models is equivalent to existence of winning strategies in associated bisimulation games.

(11)

These are two-player games, played in a (finite or infinite) number of rounds;

(12)

These are two-player games, played in a (finite or infinite) number of rounds; in every round Player I, and then Player II, picks an element from the one, respectively the other model, according to certain rules.

(13)

Player I (theSpoiler) tries to break the match between the selected elements, while Player II (the Simulator) tries to maintain it.

(14)

The Simulator has a winning strategy in this game iff there is a (finite or infinite) bisimulation between the models.

(15)

The Simulator has a winning strategy in this game iff there is a (finite or infinite) bisimulation between the models.

We illustrate such games by an example.

(16)

(17)

Let us denote by AA the logic AA extended with the modal constant π (with non-strict semantics)

AA^π+-bisimulation game: played on a pair of AA^π+-models (M₀, M₁).

(18)

Configuration: a pair of intervals ([a₀, b₀], [a₁, b₁]), such that [a₀, b₀] ∈ M₀ and [a₁, b₁] ∈ M₁.

(19)

The game starts from a given initial configuration.

(20)

At every round, given a current configuration ([a₀, b₀], [a₁, b₁]), Player I plays one of the following two moves, where i ∈ {0, 1}:

(21)

3_r-move: Player I chooses M_i and an interval [b_i, c_i];

(22)

3_l-move: Player I chooses Mi and an interval [ci, ai].

(23)

In the first case, Player II replies by choosing an interval

[b_1−i, c_1−i], which leads to the new configuration ([b₀, c₀], [b₁, c₁]).

(24)

In the second case, Player II chooses an interval [c1−i, a_1−i], which leads to the new configuration ([c₀, a₀], [c₁, a₁]).

(25)

In the second case, Player II chooses an interval [c1−i, a_1−i], which leads to the new configuration ([c₀, a₀], [c₁, a₁]).

Bisimulation games for AA⁺ and AA⁻ are defined likewise.

(26)

(27)

and truth in AA

If after any round the current configuration is not a local isomorphism, Player I wins the game; otherwise, Player II wins.

(28)

Intuitively, Player II has a winning strategy in the k-round AA-bisimulation game on the models M₀ and M₁ with a given initial configuration, if she can win regardless of the moves played by Player I; otherwise, Player I has a winning strategy.

(29)

and truth in AA

Proposition. Let P be a finite set of propositional letters. For all k ≥ 0, Player II has a winning strategy in the k-round

AA-bisimulation game on M₀ and M₁, with initial configuration ([a₀, b₀], [a₁, b₁]), iff [a₀, b₀] and [a₁, b₁] satisfy the same AA-formulas over P with modal operator depth at most k.

(30)

Proposition. Let P be a finite set of propositional letters. For all k ≥ 0, Player II has a winning strategy in the k-round

AA-bisimulation game on M₀ and M₁, with initial configuration ([a₀, b₀], [a₁, b₁]), iff [a₀, b₀] and [a₁, b₁] satisfy the same AA-formulas over P with modal operator depth at most k.

Corollary. Player II has a winning strategy in the infinite AA-bisimulation game on M₀ and M₁, with initial configuration ([a0, b₀], [a1, b₁]), iff [a0, b₀] and [a1, b₁] satisfy the same AA-formulas over P.

(31)

(32)

Proposition. The modal constant π is not definable in AA .

(33)

Proposition. The modal constant π is not definable in AA⁺. Proof. Let M = hI(Z)⁺, Vi, where all variables hold everywhere.

(34)

Proposition. The modal constant π is not definable in AA . Proof. Let M = hI(Z)⁺, Vi, where all variables hold everywhere.

The intervals [0, 1] and [1, 1] are distinguished in AA^π+ by π.

(35)

However, this pair of intervals cannot be distinguished in AA⁺.

(36)

However, this pair of intervals cannot be distinguished in AA⁺. Indeed, consider the k-round AA⁺-bisimulation game on (M, M) with initial configuration ([0, 1], [1, 1]).

(37)

Winning strategy for Player II in the AA⁺-bisimulation game with k-rounds on (M, M) with initial configuration ([0, 1], [1, 1]):

(38)

Winning strategy for Player II in the AA⁺-bisimulation game with k-rounds on (M, M) with initial configuration ([0, 1], [1, 1]):

if Player I plays a 3r-move from an interval in the current configuration, then Player II chooses any right-neighbor of the other interval in the configuration, and vice versa. The same for 3l-moves.

(39)

(40)

defined in AA .

(41)

defined in AA^π+.

Proof for the cases of hBi and hDi (the other are analogous).

(42)

defined in AA .

Consider the AA^π+-models M0= hI(Z \ {1, 2})⁺, V₀i and M₁= hI(Z)⁺, V₁i, where p holds under V1 on all intervals [a, b]

such that a < b and V₀ is the restriction of V₁ to I(Z \ {1, 2})⁺.

(43)

defined in AA^π+.

such that a < b and V₀ is the restriction of V₁ to I(Z \ {1, 2})⁺. Now, M1,[0, 3] |= hBip,

(44)

defined in AA .

such that a < b and V₀ is the restriction of V₁ to I(Z \ {1, 2})⁺. Now, M1,[0, 3] |= hBip, but M0,[0, 3] 6|= hBip.

(45)

defined in AA^π+.

such that a < b and V₀ is the restriction of V₁ to I(Z \ {1, 2})⁺. Now, M1,[0, 3] |= hBip, but M0,[0, 3] 6|= hBip. Same for hDip.

(46)

defined in AA .

Thus, it suffices to show that Player II has a winning strategy for the k-round AA^π+-bisimulation game between M₀ and M₁ with initial configuration ([0, 3], [0, 3]).

(47)

defined in AA^π+.

In fact, Player II has a uniform strategy to play forever that game:

at any position, if Player I plays a 3r-move then Player II arbitrarily chooses a right-neighbor of the current interval on the other structure,

(48)

defined in AA .

at any position, if Player I plays a 3r-move then Player II arbitrarily chooses a right-neighbor of the current interval on the other structure, with the only constraint to pick a point-interval if and only if Player I has picked a point-interval, as well.

(49)

defined in AA^π+.

at any position, if Player I plays a 3r-move then Player II arbitrarily chooses a right-neighbor of the current interval on the other structure, with the only constraint to pick a point-interval if and only if Player I has picked a point-interval, as well. Likewise, if Player I plays a 3l-move.

(50)

on the class of all interval structures over linear orders(with strict semantics). Formally, let F₁ and F₂ be any pair of such fragments.

We say that:

• F₂ isat least as expressive as F₁, denoted F₁ F₂, if every operator hX i ∈ F₁ is definable in F₂ (hX i F₂).

• F₁ isstrictly less expressive than F₂, denoted F₁≺ F₂, if F1 F2 but not F₂ F1.

• F1 and F₂ are equally expressive(or expressively equivalent), denoted F₁ ≡ F2, if F₁ F2 and F₂ F1.

• F1 and F₂ are expressively incomparable, denoted F₁6≡ F2, if neither F1 F2 nor F2 F1.

A definability hX i F is optimal if hX i 6 F^′ for any fragment F^′ such that F^′ ≺ F. A set of such definabilities is optimal if it consists of optimal definabilities.

(51)

hLip ≡ hAihAip hLi A

hOip ≡ hE ihBip hOi BE

hOip ≡ hBihE ip hOi BE

hDip ≡ hE ihBip hDi BE

hLip ≡ hBi[E ]hBihE ip hLi BE hLip ≡ hE i[B]hE ihBip hLi BE

Theorem. The above set of inter-definability equations is sound, complete, and optimal.

Soundness is easy; completeness is hard.

(52)

For each HS operator hX i, we show that hX i is not definable in any fragment of HS that does not contain as definable (according to given table) all operators of some of the fragments in which hX i is definable (according to the given table).

Formally, for each HS operator hX i, the proof consists of the following steps:

1. using the given table, find all fragments F_i such that hX i Fi;

2. identify the list M1, . . . ,Mm of all ⊆-maximal fragments of HS that contain neither the operator hX i nor any of the fragments F_i identified by the previous step;

3. for each fragment Mi, with i ∈ {1, . . . , m}, provide a bisimulation for M_i which is not a bisimulation for X.

(53)

Lemma. The set of inter-definability equations for hLi and hLi given in the table is complete.

Proof. According to the given table, hLi is definable in terms of A and BE. Hence, the fragments BEDOALEDO and BDOALBEDO are the only ⊆-maximal ones not featuring hLi and containing neither A nor BE.

To prove the thesis, it suffices to exhibit a bisimulation for each one of these two fragments that does not preserve the relation induced by hLi.

Thanks to soundness, BEDOALEDO and BDOALBEDO are expressively equivalent to BEOAED and BDOABE, respectively.

Thus, we can refer to the latter ones instead of the former ones.

We give the details for BEOAED and leave the case of BDOABE as an exercise.

(54)

let V₁ and V₂ be such that V₁(p) = {[2, 3]} and V₂(p) = ∅, where p is the only propositional letter of the language.

Moreover, let Z be a relation between (intervals of) M₁ and M₂ defined as Z = {([0, 1], [0, 1])}.

It can be easily shown that Z is a BEOAED-bisimulation.

The local property is trivially satisfied, since all Z -related intervals satisfy ¬p.

As for the forward and backward conditions, it suffices to notice that, starting from the interval [0, 1], it is not possible to reach any other interval using any of the modal operators of the fragment.

It can be easily checked that Z does not preserve the relation induced by the modality hLi. Indeed, ([0, 1], [0, 1]) ∈ Z and M₁, [0, 1] hLip, but M2,[0, 1] ¬hLip. Therefore, hLi is not definable in BEDOALEDO.

(55)

Lemma. The set of inter-definability equations for hAi and hAi given in the table is complete.

To get the requested bisimulation, we exploit a well-known property of the set of real numbers R: R (resp., Q, Q = R \ Q) can be partitioned into a countable number of pairwise disjoint subsets, each one of which is dense in R.

Formally, there are countably many nonempty sets Ri (resp., Qi, Q_i), with i ∈ N, such that, for each i ∈ N, R_i (resp., Q_i, Q_i) is dense in R, R =S

i ∈NR_i (resp., Q =S

i ∈NQ_i, Q =S

i ∈NQ_i), and R_i ∩ Rj = ∅, (resp., Qi∩ Qj = ∅, Q_i∩ Q_j = ∅), for each i , j ∈ N with i 6= j.

(56)

(57)

FO₂[<]: first-order language with equality and a countable set of binary relational symbols {P₁, P₂. . .} and a distinguished binary relation <, always interpreted as a linear order.

(58)

FO^k

2[<]: the fragment of FO2[<] involving only k individual variables x₁, . . . , x_k.

(59)

FO^k

2[<]: the fragment of FO2[<] involving only k individual variables x₁, . . . , x_k.

Hereafter we omit the lower index 2.

(60)

Let x_i, x_j, x_k be 3 distinct variables.

(61)

In what follows, ST_x^′

i,x_j,x_k(ϕ) translates the truth condition of ϕ on the current interval [xi, xj] to FO³[<]:

(62)

• ST_x^′

i,xj,xk(pn) := Pn(xi, xj),

(63)

• ST_x^′

i,xj,xk(¬ϕ) := ¬ST_x^′_i_,x_j_,x_k(ϕ),

(64)

• ST_x^′

i,x_j,x_k(ϕ1∨ ϕ2) := ST_x^′_i_,x_j_,x_k(ϕ1) ∨ ST_x^′_i_,x_j_,x_k(ϕ2),

(65)

• ST_x^′

i,x_j,x_k(hBiϕ) := ∃x_k(x_i ≤ xk < x_j ∧ ST_x^′_i_,x_k_,x_j(ϕ)),

(66)

• ST_x^′

i,xj,xk(hE iϕ) := ∃xk(xi < x_k ≤ xj ∧ ST_x^′_k_,x_j_,x_i(ϕ)),

(67)

• ST_x^′

i,xj,xk(hE iϕ) := ∃xk(xi < x_k ≤ xj ∧ ST_x^′_k_,x_j_,x_i(ϕ)),

• and likewise for hBi, hE i.

(68)

(69)

The translation extends to all formulae of HS, by suitably re-using variables, e.g.:

(70)

variables, e.g.:

ST_x^′_i_,x_j_,x_k(hOiϕ) := ∃x_k(x_i < x_k < x_j ∧

∃xi(x_j ≤ xi ∧ ST_x^′_k_,x_i_,x_j(ϕ))),

(71)

∃xi(x_j ≤ xi ∧ ST_x^′_k_,x_i_,x_j(ϕ))), ST_x^′

i,xj,xk(hDiϕ) := ∃x_k(xi ≤ xk ≤ xj ∧

∃xi(x_k ≤ xi ≤ xj ∧ ST_x^′_k_,x_i_,x_j(ϕ))).

(72)

variables, e.g.:

It works for the binary modalities C , D, T as well, e.g.:

(73)

ST_x^′_i_,x_j_,x

k(ϕC ψ) := ∃x_k(x_i ≤ xk ≤ xj∧ ST_x^′_i_,x_k_,x_j(ϕ) ∧ ST_x^′

k,xj,xi(ψ)),

(74)

variables, e.g.:

ST_x^′_i_,x_j_,x

k,xj,xi(ψ)), and likewise for D and T .

(75)

ST_x^′_i_,x_j_,x

Now, we define:

ST_x_i_,x_j_,x_k(ϕ) := xi ≤ xj ∧ ST_x^′_i_,x_j_,x_k(ϕ).

(76)

variables, e.g.:

ST_x^′_i_,x_j_,x

Now, we define:

ST_x_i_,x_j_,x_k(ϕ) := xi ≤ xj ∧ ST_x^′_i_,x_j_,x_k(ϕ).

Note that the only free variables in STxi,xj,xk(ϕ) are xi, x_j.

(77)

(78)

structure for FO[<] by interpreting P_n with V (p_n).

(79)

Every interval model M = hI(D), V i can be regarded as a structure for FO[<] by interpreting P_n with V (p_n).

Claim. For every interval model M, every interval [b, e] in M, and every formula ϕ of HS or CDT, the following holds:

M,[b, e] |= ϕ iff M STxi,xj,x_k(ϕ)[xi := b, xj := e]

where denote truth of first-order formulae.

(80)

Corollary. HS ≺ CDT FO³[<].

(81)

Every interval model M = hI(D), V i can be regarded as a structure for FO[<] by interpreting P_n with V (p_n).

Theorem. FO³[<] CDT.

Y. Venema, A modal logic for chopping intervals, Journal of Logic and Computation, 1(4):453–476, 1991

(82)

Theorem. FO³[<] CDT.

Y. Venema, A modal logic for chopping intervals, Journal of Logic and Computation, 1(4):453–476, 1991

Corollary. CDT isexpressively complete for FO³[<].

(83)

(84)

Assuming that x and y are two distinct variables, formulas of FO²[<] can be defined recursively as follows:

(85)

A₀ ::= x = x | x = y | y = x | y = y | x < y | y < x, A₁ ::= P(x, x) | P(x, y ) | P(y , x) | P(y , y ),

α ::= A₀| A1 | ¬α | α ∨ β | ∃xα | ∃y α.

(86)

A₀ ::= x = x | x = y | y = x | y = y | x < y | y < x, A₁ ::= P(x, x) | P(x, y ) | P(y , x) | P(y , y ),

α ::= A₀| A1 | ¬α | α ∨ β | ∃xα | ∃y α.

For technical convenience, we can assume that both variables x and y occur as (possibly vacuous) free variables in every formula α ∈ FO²[<], that is, α = α(x, y ).

(87)

semantic correspondence

(88)

Mappings between the models:

(89)

semantic correspondence

AA^π+-models are mapped to relational models for FO²[<] by associating a binary relation P with the valuation V (p) of every propositional variable p ∈ AP of the language of AA^π+.

(90)

Conversely, to map relational models to (non-strict) interval ones, we associate two propositional letters p^≤ and p^≥ of the interval logic with every binary relation P, as follows.

(91)

semantic correspondence

Given a relational model A = hD, VAi, the corresponding non-strict interval model ζ(A) is a pair hI(D)⁺, V_ζ(A)i such that for any binary relation P and interval [a, b]:

(92)

Given a relational model A = hD, VAi, the corresponding non-strict interval model ζ(A) is a pair hI(D)⁺, V_ζ(A)i such that for any binary relation P and interval [a, b]:

[a, b] ∈ V_ζ(A)(p^≤) iff (a, b) ∈ V_A(P),