Reachability via saturation Gabriele Puppis

(1)

Reachability via saturation

Gabriele Puppis

LaBRI / CNRS

(2)

Reachability is semi-decidable

A path connecting two sets, if exists, can be found in finitely many steps.

Forward analysis

III FFF

The problem is of course termination, namely, to detect non-reachability...

(3)

Forward analysis

III FFF

(4)

Forward analysis

III FFF

(5)

Forward analysis

III FFF

(6)

Forward analysis

III FFF

(7)

Forward analysis

III FFF

Backward analysis

III FFF

(8)

Sometimes non-reachability can be checked effectively using “safe” over-approximations of reachable sets

guess a separator

Both approaches require symbolic representations of infinite sets

(9)

a

Acceleration / pumping

III FFF

guess a separator

(10)

a a^⋆

III FFF

guess a separator

(11)

a

b a^⋆

III FFF

guess a separator

(12)

a

b a^⋆

b^⋆

III FFF

guess a separator

(13)

a

b a^⋆

b^⋆ π

III FFF

guess a separator

(14)

a

b a^⋆

b^⋆ π

π^⋆

III FFF

guess a separator

(15)

a

b a^⋆

b^⋆ π

π^⋆

III FFF

Invariant analysis

III FFF

guess a separator

(16)

a

b a^⋆

b^⋆ π

π^⋆

III FFF

Invariant analysis

III FFF

guess a separator

(17)

a

b a^⋆

b^⋆ π

π^⋆

III FFF

Invariant analysis

III FFF

guess a separator

(18)

Backward reachability for pushdown systems Given a pushdown system P = (Q, Σ, Γ, ∆) and a set B0 ⊆ Q ⋅ Γ^⋆ of target configurations, define:

Bn+1 = Bn ∪ {qz ∣ ∃q^′z^′∈Bn. ∃a ∈ Σ. qzqzqzÐÐÐÐÐÐÐÐâÐââ→ q→ q→ q^′^′^′zzz^′^′^′} Bω =

∪

_{n ∈ N}Bn

Bω contains the configurations from which one can reach B0

Bω is usually infinite, but is it perhaps regular?

Example

Consider the pushdown system

q pop γ

B0 = {qε} B1 = {qε, qγ} B2 = {qε, qγ, qγγ} . . . Bω = qε^⋆ is indeed regular, but how to efficiently compute it?

(19)

∪

_{n ∈ N}Bn

Example

q pop γ

(20)

∪

_{n ∈ N}Bn

Example

q pop γ

(21)

∪

_{n ∈ N}Bn

Example

q pop γ

B0 = {qε} B1 = {qε, qγ} B2 = {qε, qγ, qγγ} . . .

Bω = qε^⋆ is indeed regular, but how to efficiently compute it?

(22)

∪

_{n ∈ N}Bn

Example

q pop γ

B0 = {qε} B1 = {qε, qγ} B2 = {qε, qγ, qγγ} . . . B_ω = qε^⋆ is indeed regular, but how to efficiently compute it?

(23)

“Pump” the changes from B_n to B_n+1 to obtain

a new sequence C0, C1, . . . that converges more quickly:

(completeness) ∀n ∈ N. BBBⁿnn ⊆⊆⊆ CCCnnn

(soundness) ∀n ∈ N. CCCn_n_n ⊆⊆⊆ BBB_ω_ω_ω

(termination) ∃n ∈ N. CCCnn_n === CCC_n+1n+1_n+1

the limit

∪

_n∈NC_n coincides with B_ω

The sets C0, C1, . . . will be defined by

automata A₀, A₁, . . . sharing the same state spacesame state spacesame state space...

(24)

“Pump” the changes from B_n to B_n+1 to obtain

a new sequence C0, C1, . . . that converges more quickly:

(completeness) ∀n ∈ N. BBBⁿnn ⊆⊆⊆ CCCnnn

(soundness) ∀n ∈ N. CCCn_n_n ⊆⊆⊆ BBB_ω_ω_ω

(termination) ∃n ∈ N. CCCnn_n === CCC_n+1n+1_n+1

the limit

∪

_n∈NC_n coincides with B_ω

The sets C0, C1, . . . will be defined by

automata A₀, A₁, . . . sharing the same state spacesame state spacesame state space...

(25)

Initial conditions

The pushdown system P has m states q₁, . . . ,q_m

The automaton A₀ recognizing C₀=B₀ has a single initial non-final state s0, m distinct statess1, . . . ,sm, and possibly other states

No transition in A₀reaches the initial state s₀ The uniqueq_i-labelled transition in A₀is (s₀, q_i, s_i) The other transitions in A₀ are labelled by stack symbols

A₀ s₀ s₀

s1

⋮ sm

. . .

× ×

×

q1

q_m

Γ

(26)

Initial conditions

The pushdown system P has m states q₁, . . . ,q_m The automaton A₀ recognizing C₀=B₀ has a single initial non-final state s0, m distinct statess1, . . . ,sm, and possibly other states

A₀ s₀ s₀

s1

⋮ sm

. . .

× ×

×

q1

q_m

Γ

(27)

Initial conditions

No transition in A₀reaches the initial state s₀

The uniqueq_i-labelled transition in A₀is (s₀, q_i, s_i) The other transitions in A₀ are labelled by stack symbols

A₀ s₀ s₀

s1

⋮ sm

. . .

× ×

×

q1

q_m

Γ

(28)

Initial conditions

No transition in A₀reaches the initial state s₀ The uniqueq_i-labelled transition in A₀is (s₀, q_i, s_i)

The other transitions in A₀ are labelled by stack symbols

A₀ s₀ s₀

s1

⋮ sm

. . .

× ×

×

q1

q_m

Γ

(29)

Initial conditions

A₀ s₀ s₀

s1

⋮ sm

. . .

× ×

×

q1

q_m

Γ

(30)

Saturation procedure

Construct A_n+1 from A_n by adding transitions, as follows:

1 select a transition rule (qqq_i_i_iγ, a, qγγ qq_j_j_jzzz )in the pushdown system P

2 select a state sss^′^′^′ in A_n reachable fromsss₀0₀ via aqqq_j_j_jzzz-labelled path

3 add transition (sss_i_i_i, γγγ, sss^′^′^′)

A_n

s₀ s₀

si

⋮ sj

. . .

. . . qi

q_j

s^′ z

γ

Termination: straightforward Only polynomially many transitions can be added (⇒ reachability in PTIME)

Soundness: by induction on n s0

s₀ s0 qqq^′^′^′zzz^′^′^′

ÐÐÐ→

An+1 sss^′^′^′

⇓ s₀ s0

s₀ ÐÐ^qz^qz^qzÐ→

A0 sss^′^′^′ ∧ qqq^′^′^′zzz^′^′^′ ÐÐ^⋆Ð→

P qzqzqz Completeness:

∀ config. qqq_ii_iγwγwγw ∈ B_n+1∖B_n

∃ trans. qqqiiiγwγwγw ÐÐÐ^a→

P qqqjjjzwzwzw with qqqj_jjzwzwzw ∈ Bn

Select rule (qqqiiiγ, a, qγγ qqjjjzzz )in P and path sss0₀0

qjz qjz qjz

ÐÐÐ→

An sss^′^′^′ in An

to prove that qqqiiiγwγwγw ∈L (An+1)

(31)

2 select a statesss^′^′^′ in A_n reachable fromsss₀₀₀ via aqqq_j_j_jzzz-labelled path

A_n

s₀ s₀

si

⋮ sj

. . .

. . . qi

q_j

s^′ z

γ

s₀ s0 qqq^′^′^′zzz^′^′^′

ÐÐÐ→

An+1 sss^′^′^′

⇓ s₀ s0

A0 sss^′^′^′ ∧ qqq^′^′^′zzz^′^′^′ ÐÐ^⋆Ð→

qjz qjz qjz

ÐÐÐ→

(32)

A_n

s₀ s₀

si

⋮ sj

. . .

. . . qi

q_j

s^′ z

γ

s₀ s0 qqq^′^′^′zzz^′^′^′

ÐÐÐ→

An+1 sss^′^′^′

⇓ s₀ s0

A0 sss^′^′^′ ∧ qqq^′^′^′zzz^′^′^′ ÐÐ^⋆Ð→

qjz qjz qjz

ÐÐÐ→

(33)

A_n

s₀ s₀

si

⋮ sj

. . .

. . . qi

q_j

s^′ z

γ

s₀ s0 qqq^′^′^′zzz^′^′^′

ÐÐÐ→

An+1 sss^′^′^′

⇓ s₀ s0

A0 sss^′^′^′ ∧ qqq^′^′^′zzz^′^′^′ ÐÐ^⋆Ð→

qjz qjz qjz

ÐÐÐ→

(34)

A_n

s₀ s₀

si

⋮ sj

. . .

. . . qi

q_j

s^′ z

γ

s₀ s0 qqq^′^′^′zzz^′^′^′

ÐÐÐ→

An+1 sss^′^′^′

⇓ s₀ s0

A0 sss^′^′^′ ∧ qqq^′^′^′zzz^′^′^′ ÐÐ^⋆Ð→

P qzqzqz

Completeness:

qjz qjz qjz

ÐÐÐ→

(35)

A_n

s₀ s₀

si

⋮ sj

. . .

. . . qi

q_j

s^′ z

γ

s₀ s0 qqq^′^′^′zzz^′^′^′

ÐÐÐ→

An+1 sss^′^′^′

⇓ s₀ s0

A0 sss^′^′^′ ∧ qqq^′^′^′zzz^′^′^′ ÐÐ^⋆Ð→

Select rule (qqq_ii_iγ, a, qγγ qq_jj_jzzz )in P and path sss0₀0

qjz qjz qjz

ÐÐÐ→

(36)

Example

Consider the target set B0 = {q2γ1γ2γ3}over the pushdown system

q1 q2

γ6

γ₆ γ6/εεε γ6/ε

γ5/γ4γ3

γ4

γ₄ γ4/γγγ1₁1γγγ2₂2

γ4/γ1γ2

s0

s₁

s₂ s₃ s₄ s₅

q1

q₂

γ1

γγγ111 γ2 γγγγ3333

C0= {q2γ1γ2γ3}

C1= {q2γ1γ2γ3, q2γ4γ3} C2= {q2γ1γ2γ3, q2γ4γ3, q1γ5} C3= {q2γ1γ2γ3, q2γ4γ3, q1γ6γ5}

(37)

Example

q1 q2

γ6

γ5/γ4γ3

γ4

s0

s₁

s₂ s₃ s₄ s₅

q1

qqq2₂2

γ1

γγ11

γ1

γγ11 γγγγγγ222222 γγγγ3333

γ4

γ₄ γ4

C0= {q2γ1γ2γ3}

(38)

Example

q1 q2

γ6

γ5/γ4γ3

γ4

γ4/γ1γ2

s0

s₁

s₂ s₃ s₄ s₅

q1

q₂

γ1

γ₄

C0= {q2γ1γ2γ3}

(39)

Example

q1 q2

γ6

γ5

γ5/γγγ444γγγ333

γ4

γ4/γ1γ2

s0

s₁

s₂ s₃ s₄ s₅

q1

qqq2₂2

γ1

γγγ111 γ2 γγγγγγ333333

γ4

γ₄ γ4

γγγ5₅5

C0= {q2γ1γ2γ3}

(40)

Example

q1 q2

γ6

γ5/γ4γ3

γ4

γ4/γ1γ2

s0

s₁

s₂ s₃ s₄ s₅

q1

q₂

γ1

γ₄

γ5

C0= {q2γ1γ2γ3}

(41)

Example

q1 q2

γ6

γ₆ γ6/εεε γ6

γ₆ γ6/εεε

γ5/γ4γ3

γ4

γ4/γ1γ2

s0

s₁

s₂ s₃ s₄ s₅

qqq111

q₂

γ1

γ₄

γ5

γ₆ γ₆ γ₆

C0= {q2γ1γ2γ3}

(42)

Example

q1 q2

γ6

γ5/γ4γ3

γ4

γ4/γ1γ2

s0

s₁

s₂ s₃ s₄ s₅

q1

q₂

γ1

γ₄

γ5

γ₆

C0= {q2γ1γ2γ3}

C1= {q2γ1γ2γ3, q2γ4γ3} C2= {q2γ1γ2γ3, q2γ4γ3, q1γ5} C₃= {q₂γ₁γ₂γ₃, q₂γ₄γ₃, q₁γ₆^⋆γ₅}

=B_ω

(43)

Theorem (Bouajjani, Esparza & Maler ’97)

Given a pushdown system P and a regular set B of configurations, the set of configurations that can reach B

is regular and can be computed in polynomial time.

Similar generalizations can be proved for:

tree rewriting systems (L¨oding ’06, . . . )

reachability games on higher-order pushdown systems (Bouajjani & Meyer ’04, Hague & Ong ’07, . . . )

. . .

(44)

Given an alternatingalternatingalternating pushdown system P and a regular set B of conf., the winning regionwinning regionwinning region for the B-reachability gameB-reachability gameB-reachability game

. . .

(45)

Given an alternatingalternatingalternating pushdown system P and a regular set B of conf., the winning regionwinning regionwinning region for the B-reachability gameB-reachability gameB-reachability game

. . .

(46)

Next we will focus on reachability for systems that use variables over natural numbers instead of a stack...

(x , y ) ∶= (0, 0) (x , y ) ∶= (0, 0) (x , y ) ∶= (0, 0) while (x , y ) ≠ (0, 1)(x , y ) ≠ (0, 1)(x , y ) ≠ (0, 1) do

if [input is north west] then (x , y ) ∶= (x , y ) + (1, 3)(x , y ) ∶= (x , y ) + (1, 3)(x , y ) ∶= (x , y ) + (1, 3) else if [input is north east] then

(x , y ) ∶= (x , y ) + (−1, 1)(x , y ) ∶= (x , y ) + (−1, 1)(x , y ) ∶= (x , y ) + (−1, 1) else if [input is south] then (x , y ) ∶= (x , y ) + (0, −2)(x , y ) ∶= (x , y ) + (0, −2)(x , y ) ∶= (x , y ) + (0, −2)

x y

?

Definition

A vector addition system (VAS) is a transition system (N^k, ∆), where ∆ is a finite subset of Z^k and

¯

x ÐÐÐ→ ¯y

¯

x ÐÐÐ→ ¯y

¯

x ÐÐÐ→ ¯y iff

⎧⎪

⎪

⎨

⎪⎪

⎩

¯ x , ¯¯ y ≥ 0 x , ¯¯ y ≥ 0 x , ¯y ≥ 0

¯

y − ¯¯ x ∈ ∆ y − ¯¯ x ∈ ∆ y − ¯x ∈ ∆

(47)

Next we will focus on reachability for systems that use variables over natural numbers instead of a stack...

(x , y ) ∶= (0, 0) (x , y ) ∶= (0, 0) (x , y ) ∶= (0, 0) while (x , y ) ≠ (0, 1)(x , y ) ≠ (0, 1)(x , y ) ≠ (0, 1) do

if [input is north west] then (x , y ) ∶= (x , y ) + (1, 3)(x , y ) ∶= (x , y ) + (1, 3)(x , y ) ∶= (x , y ) + (1, 3) else if [input is north east] then

(x , y ) ∶= (x , y ) + (−1, 1)(x , y ) ∶= (x , y ) + (−1, 1)(x , y ) ∶= (x , y ) + (−1, 1) else if [input is south] then (x , y ) ∶= (x , y ) + (0, −2)(x , y ) ∶= (x , y ) + (0, −2)(x , y ) ∶= (x , y ) + (0, −2)

x y

?

Definition

A vector addition system (VAS) is a transition system (N^k, ∆), where ∆ is a finite subset of Z^k and

¯

x ÐÐÐ→ ¯y

¯

x ÐÐÐ→ ¯y

¯

x ÐÐÐ→ ¯y iff

⎧⎪

⎪

⎨

⎪⎪

⎩

¯ x , ¯¯ y ≥ 0 x , ¯¯ y ≥ 0 x , ¯y ≥ 0

¯

y − ¯¯ x ∈ ∆ y − ¯¯ x ∈ ∆ y − ¯x ∈ ∆

(48)

Definition

A lossy VAS is a transition system (N^k, ∆), where ∆ is a finite subset of Q × Z^k ×Q and

¯x ÐÐÐ→ ¯y

¯x ÐÐÐ→ ¯y iff

⎧⎪

⎪⎪

⎨

⎪⎪

⎪⎩

¯ x , ¯¯x , ¯¯x , ¯y ≥ 0y ≥ 0y ≥ 0

¯

y¯yy¯^′^′^′−−−x ∈ ∆¯x ∈ ∆¯x ∈ ∆¯ for some ¯y^′≥y¯

A VAS with states is a transition system (Q × N^k, ∆), where ∆ is a finite subset of Q × Z^k ×Q and

(p, ¯x ) ÐÐÐ→ (q, ¯y ) (p, ¯x ) ÐÐÐ→ (q, ¯y ) (p, ¯x ) ÐÐÐ→ (q, ¯y ) iff

⎧⎪

⎪⎪

⎨

⎪⎪

⎪⎩

¯ x , ¯¯x , ¯¯x , ¯y ≥ 0y ≥ 0y ≥ 0

(p, ¯(p, ¯(p, ¯y − ¯y − ¯y − ¯x , q) ∈ ∆x , q) ∈ ∆x , q) ∈ ∆

States do not add power, as they can be implemented by counters e.g. 2 states = 2 additional counters that sum up to 1

(p, ¯x ) ÐÐ→ (q, ¯y ) becomes (0, 1, ¯x ) ÐÐ→ (1, 0, ¯y )

(49)

Definition

¯x ÐÐÐ→ ¯y

⎧⎪

⎪⎪

⎨

⎪⎪

⎪⎩

¯ x , ¯¯x , ¯¯x , ¯y ≥ 0y ≥ 0y ≥ 0

¯

⎧⎪

⎪⎪

⎨

⎪⎪

⎪⎩

¯ x , ¯¯x , ¯¯x , ¯y ≥ 0y ≥ 0y ≥ 0

(p, ¯(p, ¯(p, ¯y − ¯y − ¯y − ¯x , q) ∈ ∆x , q) ∈ ∆x , q) ∈ ∆

(50)

Definition

¯x ÐÐÐ→ ¯y

⎧⎪

⎪⎪

⎨

⎪⎪

⎪⎩

¯ x , ¯¯x , ¯¯x , ¯y ≥ 0y ≥ 0y ≥ 0

¯

⎧⎪

⎪⎪

⎨

⎪⎪

⎪⎩

¯ x , ¯¯x , ¯¯x , ¯y ≥ 0y ≥ 0y ≥ 0

(p, ¯(p, ¯(p, ¯y − ¯y − ¯y − ¯x , q) ∈ ∆x , q) ∈ ∆x , q) ∈ ∆

(51)

VAS are the same as Petri nets:

configurations = tokens per location (e.g. (2, 1, 3, 0, 0)) transitions = transfers of tokens (e.g. (0, −1, −1, 0, 1))

(52)

(53)

(54)

(55)

(56)

(57)

(58)

(59)

(60)

(61)

We may expect that reachable sets are linear...

but they are not!

(0, 0)

+ (3, 1)N + (−1, 1)N + (0, −2)N

Theorem (Ginsburg ’66) Finite unions of linear sets are precisely the Presburger sets i.e. sets definable in FO[N, +]FO[N, +]FO[N, +] e.g. ϕ(x , y ) = ∃z . x + y = z + z

x + y x y

(x + y ) ≤ zzz ≤ O((x + y )²)

(62)

but they are not!

(0, 0) + (3, 1)N

+ (−1, 1)N + (0, −2)N

x + y x y

(x + y ) ≤ zzz ≤ O((x + y )²)

(63)

but they are not!

(0, 0) + (3, 1)N + (−1, 1)N

+ (0, −2)N

x + y x y

(x + y ) ≤ zzz ≤ O((x + y )²)

(64)

but they are not!

(0, 0) + (3, 1)N + (−1, 1)N + (0, −2)N

x + y x y

(x + y ) ≤ zzz ≤ O((x + y )²)