One-Pass and Tree-Shaped Tableaux for LTL

(1)

One-Pass and Tree-Shaped Tableaux for LTL

Nicola Gigante

(2)

Linear Temporal Logic

Linear Temporal Logic(LTL) is a propositional modal logic interpreted over inﬁnite, discrete, linear orders.

X α αwill be true at thenextstate.

αU β βwill eventually be true, and αalways holdsuntilthen.

F β≡ ⊤ U β β willeventuallybe true.

G β≡ ¬ F ¬β β willalwaysbe true.

(3)

Tableau methods for LTL satisﬁability

LTLsatisﬁabilityis the problem of checking whether there exists a model that satisﬁes a given LTL formula.

PSPACE-completeproblem.

Algorithmic solutions:

(Büchi) Automata-based Tableaumethods Temporal resolution

Reduction to model checking

…

(4)

Tableau methods for LTL satisﬁability

You have already seen a tableau method for LTL satisﬁability, which isgraph-shaped:

A graph structure is built from the closure of the formula Each node is anatom, a set of locally consistent formulae A path in the graph corresponds to a potential model of the formula

A strongly connected components decomposition of the graph is used to check whether there exists a fulﬁlling path.

(5)

A One-Pass Tree-Shaped Tableau for LTL

Today we’ll look at a different method, which isone-passand tree-shaped.

The built structure is atreeinstead of a graph.

Asingle passis sufﬁcient to build a branch of the tree and determine its acceptance or rejection.

Verysimplerule-based structure:

Easy toextendto LTL extensions Easy to parallelize

(6)

How it works

(7)

How it works

The tableau for ϕ is a tree where each node is labeled by a set of formulae, with the root labeled with{ϕ}.

The formula starts in Negated Normal Form.

At each step some rules are applied to a leaf, depending on the contents of the label, possibly generating new children for the current node.

Some rules canaccepta branch, others canrejectit.

If the complete tree contains at least an accepted branch, the formula issatisﬁable.

(8)

Expansion rules

Expansion rules are applied to a node until no other expansion rule can be applied anymore:

Boolean connectives handled just like in classical propositional tableau.

{α ∨ β}

{α} {β}

{α ∧ β}

{α, β}

(9)

Expansion rules

Expansion rules are applied to a node until no other expansion rule can be applied anymore:

Common expansion rules handle temporal operators:

{α Uβ}

{β} {α, X(α Uβ)}

{Fβ} {β} {X Fβ}

{G α}

{α, X G α}

βis called aneventuality.

X(αU β) is anX-eventuality.

(10)

Expansion rules

Rule ϕ Γ1(ϕ) Γ2(ϕ) Disjunction α∨ β {α} {β}

Until αU β {β} {α, X(α U β)}

Release αR β {α, β} {β, X(α R β)}

Eventually F β {β} {X F β}

Conjunction α∧ β {α, β}

Always G α {α, X G α}

(11)

Advancing to the next temporal step

Eventually we reach apoisednode, labelled only ofelementary formulae: propositionsortomorrows.

We can step to the next temporal state by the step rule:

{. . . , X α, . . .}

{α}

The poised node give us theevaluationfor the currentstate.

(12)

Contradictions

If a label contains contradictions, werejectthe branch.

{. . . , p, . . . , ¬p, . . .}

7

(13)

Acceptance and contradictions

If a step rule results into an empty label, we’re done:

the branch isaccepted.

{. . . , p, ¬q, r, . . .}

{}

3

(14)

Finding periodic models - loop rule

Some formulae (e.g., G F p) require to satisfy inﬁnitely often the same request, thus the labels may never become empty.

these formulae will have inﬁnite periodic models the loop rule accepts such branches

(15)

Finding periodic models - loop rule

Let u =⟨u0, . . . ,u_k⟩ be a branch with a poised leaf uk: loop rule

The branch isacceptedif there is another position i < k such that Γ(uj) = Γ (uk), and all the X-eventualities requested in uj

are fulﬁlled in u_[j+1,k].

(16)

Example

{G F(p ∧ X ¬p)}

{ F(p ∧ X ¬p), X G F(p ∧ X ¬p)}

. . . {p, X ¬p, X G F(p ∧ X ¬p)}

{¬p, G F(p ∧ X ¬p)}

{¬p, F(p ∧ X ¬p), X G F(p ∧ X ¬p)}

{¬p, p, X ¬p, . . .} {¬p, X F(p ∧ X ¬p), X G F(p ∧ X ¬p)}

3

p ¬p p ¬p

(17)

Example

{G F(p ∧ X ¬p)}

{ F(p ∧ X ¬p), X G F(p ∧ X ¬p)}

. . . {p, X ¬p, X G F(p ∧ X ¬p)}

{¬p, G F(p ∧ X ¬p)}

{¬p, F(p ∧ X ¬p), X G F(p ∧ X ¬p)}

3

p ¬p p ¬p

(18)

Example

{G F(p ∧ X ¬p)}

{F(p∧ X ¬p),X G F(p∧ X ¬p)}

. . . {p,X¬p,X G F(p∧ X ¬p)}

{¬p, G F(p ∧ X ¬p)}

{¬p, F(p ∧ X ¬p), X G F(p ∧ X ¬p)}

3

p ¬p p ¬p

(19)

{G F(p ∧ X ¬p)}

{ F(p ∧ X ¬p), X G F(p ∧ X ¬p)}

. . . {p, X ¬p, X G F(p ∧ X ¬p)}

{¬p, G F(p ∧ X ¬p)}

{¬p, F(p∧ X ¬p),X G F(p∧ X ¬p)}

{¬p,p,X¬p, . . .} {¬p, X F(p ∧ X ¬p), X G F(p ∧ X ¬p)}

3

p

¬p p ¬p

(23)

Example

{G F(p ∧ X ¬p)}

{ F(p ∧ X ¬p), X G F(p ∧ X ¬p)}

. . . {p, X ¬p, X G F(p ∧ X ¬p)}

{¬p, G F(p ∧ X ¬p)}

{¬p, F(p∧ X ¬p),X G F(p∧ X ¬p)}

{¬p, p, X ¬p, . . .} {¬p,X F(p∧ X ¬p),X G F(p∧ X ¬p)}

3

p

¬p p ¬p

(24)

Example

{G F(p ∧ X ¬p)}

{ F(p ∧ X ¬p), X G F(p ∧ X ¬p)}

. . . {p, X ¬p, X G F(p ∧ X ¬p)}

{¬p, G F(p ∧ X ¬p)}

{¬p, F(p ∧ X ¬p), X G F(p ∧ X ¬p)}

{¬p, p, X ¬p, . . .} {¬p,X F(p∧ X ¬p),X G F(p∧ X ¬p)}

3

p

¬p p ¬p

(25)

Example

{G F(p ∧ X ¬p)}

{ F(p ∧ X ¬p), X G F(p ∧ X ¬p)}

. . . {p, X ¬p, X G F(p ∧ X ¬p)}

{¬p, G F(p ∧ X ¬p)}

{¬p, F(p ∧ X ¬p), X G F(p ∧ X ¬p)}

{¬p, p, X ¬p, . . .} {¬p,X F(p∧ X ¬p), X G F(p ∧ X ¬p)}

3

p ¬p

(26)

Example

{G F(p ∧ X ¬p)}

{ F(p ∧ X ¬p), X G F(p ∧ X ¬p)}

. . . {p, X ¬p, X G F(p ∧ X ¬p)}

{¬p, G F(p ∧ X ¬p)}

{¬p, F(p ∧ X ¬p), X G F(p ∧ X ¬p)}

3

p ¬p

(27)

Example

{G F(p ∧ X ¬p)}

{ F(p ∧ X ¬p), X G F(p ∧ X ¬p)}

. . . {p,X¬p,X G F(p∧ X ¬p)}

{¬p, G F(p ∧ X ¬p)}

{¬p, F(p ∧ X ¬p), X G F(p ∧ X ¬p)}

3

p ¬p

(28)

Example

{G F(p ∧ X ¬p)}

7

{G ¬p, q U p}

7

(40)

Example - unsatisﬁable formula

{G ¬p ∧ q U p}

{ G ¬p, q U p}

{¬p, X G ¬p, p}

7

{¬p, X G ¬p, q, X(q U p)}

{ G ¬p, q U p}

{¬p, X G ¬p, p}

7

{¬p, X G ¬p, q, X(q U p)}

{G ¬p, q U p}

(41)

How it works - summary

To summarize:

When toaccepta branch?

When the label isempty

When we are looping while satisfying all theeventualities When to reject a branch?

When a label is contradictory

When we are looping but unable to satisfy all the eventualities

(42)

How it works - summary

To summarize:

When to accept a branch?

When the label is empty

When we are looping while satisfying all the eventualities When torejecta branch?

When a label iscontradictory

When we are looping but unable to satisfy all theeventualities

(43)

Proofs

We can brieﬂy overview how to prove that the method is soundandcomplete.

Soudness

If the complete tableau for ϕ contains anacceptedbranch, then ϕ issatisﬁable.

Completeness

If ϕ issatisﬁable, then the complete tableau for ϕ contains at

(44)

Soundness

The soundness proof builds a model from the accepted branch:

let u =⟨u0, . . . ,un⟩ be an accepted branch (unisticked) let π =⟨π0, . . . , π_m⟩ be the subsequence of itspoisednodes if u is accepted then either Γ(πm)is empty or there is a π_k with Γ(πk) = Γ (πm)that triggered the loop rule.

we extend π ad inﬁnitum to:

Π = π_[0,k](π_[k+1,m])^ω (let k = m − 1 in the empty case)

(45)

Soundness

The soundness proof builds a model from the accepted branch:

then, we can extract a model σ =⟨σ0, σ₁, . . .⟩ from Π:

σ,i|= p if and only if p ∈ Γ(Πi)

we can prove by structural induction that if ψ∈ Γ(Πi), then σ, i|= ψ:

if p∈ Γ(Π_i), it holds by deﬁnition

if X ψ∈ Γ(Π_i), either ψ∈ Γ(Π_i+1)by the step rule, or Π_i= Π_m= Π_kbecause of the loop rule, hence ψ∈ Γ(Πi+1) = Γ (Π_k+1)again because of the step rule.

all other cases follow the expansion rules, e.g. if α∨ β ∈ Γ(Π), then either α∈ Γ(Π)or β∈ Γ(Π)by

(46)

Completeness

(47)

Completeness

The completeness proof revolves around the prune rule.

(48)

Atoms and pre-models

We need a different but related concept ofatom:

Deﬁnition

Let X⊆ C(ϕ) be a set of formulae. Anatomgenerated by X is a minimalset of formulae ∆⊆ C(ϕ) such that:

X⊆ ∆

if ψ∈ ∆, then Γ1(ψ)⊆ ∆ or Γ2(ψ)⊆ ∆

(49)

Atoms and pre-models

A pre-models is a sequence of atoms that abstracts a set of models of a formula.

Deﬁnition

Apre-modelgenerated by a set X⊆ C(ϕ) is an inﬁnite sequence of atoms ∆ =⟨∆0, ∆₁, . . .⟩ such that:

∆₀is generated by X;

for all i⩾ 0, ∆i+1is generated by X(∆_i) where X(∆) ={ψ | X ψ ∈ ∆};

if αU β ∈ ∆i, then there is a k⩾ k such that β ∈ ∆k,

(50)

Atoms and pre-models

Pre-models abstract models for a formula:

A set of models for ϕ can be extracted by a pre-model ∆ A pre-model ∆ can be built from a model σ for ϕ such that if ψ∈ ∆ithen σ, i|= ψ

(51)

Finding the accepted branch

The tableau nodes can be used to build atoms:

get the sequence π =⟨π0, . . . , π_m⟩ of a branch’s poised nodes

∆(π_i), theatomof π_i, is the union of all the nodes that got expandedto reach πi.

∆(π_i)isgeneratedby X(Γ(π_i−1)).

(52)

Finding the accepted branch

So suppose a model for ϕ exists:

make a pre-model ∆ for ϕ

use ∆ as a guide totraversethe tableau for ϕ:

ﬁnd a branch u =⟨u0, . . . ,un⟩ s.t. if ∆(u_i) = ∆_ifor all i⩾ 0 the branch cannot berejectedby the contradiction rule, because otherwise we would have{p, ¬p} ⊆ ∆n.

so either the branch is accepted, and we are done, or it has been rejected by the prune rule.

(53)

Greedy pre-models

Let ∆ ={∆0, ∆1, . . .} be a pre-model for ϕ. For each X-eventuality ψ≡ X(α U β) ∈ C(ϕ) and position i ⩾ 0, let:

d_i(ψ) =







0 if ψ isnotrequested at position i n if ψ is requested at position i

and fulﬁlled at j > i such that n = j − 1

ψ₁≡ X(α U β)

ψ2≡ X(α U γ) β γ

d 3

(54)

Greedy pre-models

d_i(ψ) =







ψ₁≡ X(α U β)

d 2

(55)

Greedy pre-models

d_i(ψ) =







ψ₁≡ X(α U β)

d 1

(56)

Greedy pre-models

d_i(ψ) =







ψ₁≡ X(α U β)

d 0

(57)

Greedy pre-models

With delays, we can deﬁne apreorderon pre-models.

Given two premodels ∆ and ∆^′:

d_i⩽ d_i^′iff d_i(ψ)⩽ d_i^′(ψ)for all X-eventualities ψ

∆_i⪯ ∆_i^′iff d_i⩽ d_i^′

the order on pre-models is deﬁnedlexicographically:

∆⪯ ∆^′iff ∆_j ⩽ ∆_j^′for some j⩾ 0 with ∆i = ∆_i^′for all i < j.

(58)

Existence of greedy pre-models

If there is a pre-model ∆ for ϕ, then there is agreedyone ∆^′ ⪯ ∆.

∆⁰₀ ∆⁰₁ ∆⁰₂ · · · ∆⁰n · · ·

⪯

∆¹₀ ∆¹₁ ∆¹₂ · · · ∆¹_n · · ·

⪯

∆²₀ ∆²₁ ∆²₂ · · · ∆²n · · ·

∼ = ⪯

∆³₀ ∆³₁ ∆³₂ · · · ∆³_n · · ·

∼ = ∼ = ⪯

An inﬁnite descending chains of pre-models might exists

but, for any m the preﬁx of length m stabilizes sooner or later hence thelimitof the sequence is a pre-model, and is greedy.

(59)

Completeness: Endgame

Greedy pre-models allow us to prove completeness:

Traverse the tableau tree as described before, but suppose to do it with agreedypre-model ∆ for the formula ϕ Recall that we found a branch u with poised nodes π such that ∆(π_i) = ∆_i

Recall that by construction, it can only have been crossed by the prune rule, if at all

Let’s show this cannot happen.

(60)

Completeness: Endgame

X F α X F β X F γ 1 2

8 α β

5 α

X F α X F β X F γ n 1

2 β γ

1 2 5

α β n

1 2

β γ

(61)

Completeness: Endgame

8 α β

5 α

2 β γ

1 2 5

α β n

1 2

β γ

(62)

Completeness: Endgame

8 α β

5 α

2 β γ

1 2 5

α β n

1 2

β γ

(63)

Completeness: Endgame

8 α β

5 α

2 β γ

1 2 5

α β n

1 2

β γ

(64)

Completeness: Endgame

8 α β

5 α

2 β γ

1 2 5

α β n

1 2

β γ

(65)

The end

Questions?

(66)

Appendix

(67)

Why three occurrences?

Consider this formula:

ϕ≡ p ∧ G(p ←→ X ¬p) ∧ G F q1∧ G F q2∧

G¬(q1∧ q2)∧ G(q1−→ ¬p) ∧ G(q2−→ ¬p)

And its tableau: {ϕ}

{. . . , X F q1,X F q2, . . .}

. . . {. . . , X F q1,X F q2, . . .}

7 ?

. . . {. . . , X F q1,X F q2, . . .}

3

q2

q1

p q1 p q2 p q1

(68)

Why three occurrences?

ϕ≡ p ∧ G(p ←→ X ¬p) ∧ G F q1∧ G F q2∧

G¬(q1∧ q2)∧ G(q1−→ ¬p) ∧ G(q2−→ ¬p) And its tableau:

{ϕ}

{. . . , X F q1,X F q2, . . .}

. . . {. . . , X F q1,X F q2, . . .}

7 ?

3

q1

p q1 p q2 p q1

(69)

Why three occurrences?

ϕ≡ p ∧ G(p ←→ X ¬p) ∧ G F q1∧ G F q2∧

{ϕ}

{. . . , X F q1,X F q2, . . .}

. . . {. . . , X F q1,X F q2, . . .}

7 ?

3

q1

p q1 p q2 p q1

(70)

Why three occurrences?

ϕ≡ p ∧ G(p ←→ X ¬p) ∧ G F q1∧ G F q2∧

{ϕ}

{. . . ,X F q1,X F q2, . . .}

. . . {. . . ,X F q1,X F q2, . . .}

3

q1

p q1 p q2 p q1

(71)

Why three occurrences?

ϕ≡ p ∧ G(p ←→ X ¬p) ∧ G F q1∧ G F q2∧

{ϕ}

{. . . ,X F q1,X F q2, . . .}

. . . {. . . ,X F q1,X F q2, . . .}

7 ?

3

q1

p q1 p q2 p q1

(72)

Why three occurrences?

ϕ≡ p ∧ G(p ←→ X ¬p) ∧ G F q1∧ G F q2∧

{ϕ}

{. . . ,X F q1,X F q2, . . .}

. . . {. . . , X F q1,X F q2, . . .}

7 ?

q q1

p q1 p q2 p q1