8 AN EQUIVALENT GREATEST FIXPOINT ALGORITHM

Let us assume that𝑔 : 𝐶 → 𝐶 is a monotonic function on a complete lattice ⟨𝐶, ≤, ∨, ∧⟩ which admits its unique right-adjoint𝑔 : 𝐶 → 𝐶, i.e., ∀𝑐, 𝑐e ^′ ∈ 𝐶, 𝑔(𝑐) ≤ 𝑐^′ ⇔ 𝑐 ≤ e𝑔(𝑐^′) holds. Then, Cousot [2000, Theorem 4] shows that the following equivalence holds: for all𝑐, 𝑐^′∈ 𝐶,

lfp(𝜆𝑥. 𝑐 ∨ 𝑔(𝑥)) ≤ 𝑐^′ ⇔ 𝑐 ≤ gfp(𝜆𝑦. 𝑐^′∧ e𝑔(𝑦)) . (24) This property has been used in [Cousot 2000] to derive equivalent least/greatest fixpoint-based invariance proof methods for programs. In the following, we use (24) to derive an algorithm for deciding the inclusionL(A1) ⊆ L(A2), which relies on the computation of a greatest fixpoint rather than a least fixpoint. This can be achieved by exploiting the following simple observation, which defines an adjunction between concatenation and quotients of sets of words.

Lemma 8.1. For all𝑋, 𝑌 ∈ ℘(Σ^∗) and 𝑤 ∈ Σ^∗,𝑤𝑌 ⊆ 𝑍 ⇔ 𝑌 ⊆ 𝑤⁻¹𝑍 and 𝑌𝑤 ⊆ 𝑍 ⇔ 𝑌 ⊆ 𝑍𝑤⁻¹. PRoof. By definition, for all𝑢 ∈ Σ^∗,𝑢 ∈ 𝑤⁻¹𝑍 iff 𝑤𝑢 ∈ 𝑍. Hence, 𝑌 ⊆ 𝑤⁻¹𝑍 ⇔ ∀𝑢 ∈ 𝑌, 𝑤𝑢 ∈

𝑍 ⇔ 𝑤𝑌 ⊆ 𝑍. Symmetrically, 𝑌𝑤 ⊆ 𝑍 ⇔ 𝑌 ⊆ 𝑍𝑤⁻¹holds. □

Given a FAA = ⟨𝑄, 𝛿, 𝐼, 𝐹, Σ⟩, we define the function gPre_A :℘(Σ^∗)^{|𝑄 |} → ℘(Σ^∗)^{|𝑄 |}on𝑄-indexed vectors of sets of words as follows:

gPre_A(⟨𝑋𝑞⟩𝑞∈𝑄) ≜ ⟨Ñ

𝑎∈Σ,𝑞^′∈𝛿 (𝑞,𝑎) 𝑎⁻¹𝑋𝑞⟩𝑞^′∈𝑄 , where, as usual,Ñ

∅ = Σ^∗. It turns out that gPre_A is the usual weakest liberal precondition which is right-adjoint of Pre_A.

Lemma 8.2. For all #»𝑿, #»𝒀 ∈ ℘(Σ^∗)^{|𝑄 |}, Pre_A( #»𝑿) ⊆ #»𝒀 ⇔ #»𝑿 ⊆ gPre_A( #»𝒀 ).

PRoof.

Pre_A(⟨𝑋𝑞⟩𝑞∈𝑄) ⊆ ⟨𝑌𝑞⟩𝑞∈𝑄⇔ [by definition of Pre_A]

∀𝑞 ∈ 𝑄,Ð

𝑞→𝑞^{𝑎 ′}𝑎𝑋𝑞^′⊆ 𝑌𝑞⇔ [by set theory]

∀𝑞, 𝑞^′∈ 𝑄, 𝑞→ 𝑞^{𝑎 ′}⇒ 𝑎𝑋𝑞^′⊆ 𝑌𝑞⇔ [by Lemma 8.1]

∀𝑞, 𝑞^′∈ 𝑄, 𝑞→ 𝑞^{𝑎 ′}⇒ 𝑋𝑞^′ ⊆ 𝑎⁻¹𝑌𝑞⇔ [by set theory]

∀𝑞^′∈ 𝑄, 𝑋𝑞^′ ⊆Ñ

𝑞→𝑞^{𝑎 ′}𝑎⁻¹𝑌𝑞⇔ [by definition of gPre_A]

⟨𝑋𝑞⟩𝑞∈𝑄 ⊆ gPre_A(⟨𝑌𝑞⟩𝑞∈𝑄) . □

Hence, from equivalences (10) and (24), we obtain that for all FAsA1and𝐿2∈ ℘(Σ^∗):

L(A1) ⊆ 𝐿2 ⇔ #»𝝐^𝐹1 ⊆ gfp(𝜆 #»𝑿 . # »𝑳2𝐼1∩ gPre_A1( #»𝑿)) . (25) The following algorithm FAIncGfp decides the inclusionL(A1) ⊆ 𝐿2, when𝐿2 is regular, by implementing the greatest fixpoint computation in equivalence (25).

FAIncGfp: Greatest fixpoint algorithm forL(A1) ⊆ 𝐿2

Data: FAA1=⟨𝑄1, 𝛿1, 𝐼1, 𝐹1, Σ⟩; regular language 𝐿2.

1 ⟨𝑌𝑞⟩𝑞∈𝑄 :=Kleene(⊇, 𝜆 #»𝑿 . # »𝑳2𝐼1∩ gPre_A1( #»𝑿),𝚺# »^∗);

2 forall𝑞 ∈ 𝐹1do

3 if𝜖 ∉ 𝑌_𝑞then return false;

4 return true;

The intuition behind Algorithm FAIncGfp is that

L(A1) ⊆ 𝐿2⇔ ∀𝑤 ∈ L(A1), (𝜖 ∈ 𝑤⁻¹𝐿2⇔ 𝜖 ∈Ñ

𝑤 ∈L (A1)𝑤⁻¹𝐿2) .

Therefore, FAIncGfp computes the setÑ{𝑤⁻¹𝐿2| 𝑤 ∈ L(A1)} by using the automaton A1and by considering prefixes ofL(A1) of increasing lengths. This means that after 𝑛 iterations of Kleene, the algorithm FAIncGfp has computed

Ñ{𝑤⁻¹𝐿2 | 𝑤𝑢 ∈ L(A1), |𝑤 | ≤ 𝑛, 𝑞0∈ 𝐼1, 𝑞0 𝑤

{ 𝑞}

for every state𝑞 ∈ 𝑄1. The regularity of 𝐿2 and the property of regular languages of being closed under intersections and quotients entail that each Kleene iterate of Kleene(⊇, 𝜆 #»𝑿 . # »𝑳2𝐼1∩ gPre_A1( #»𝑿),𝚺# »^∗) is a (computable) regular language. To the best of our knowledge, this gfp-based language inclusion algorithm FAIncGfp has never been described in the literature before.

Next, we discharge the fundamental assumption guaranteeing the correctness of this algorithm FAIncGfp: the Kleene iterates computed by FAIncGfp are finitely many. To achieve this, we con-sider an abstract version of the greatest fixpoint computation exploiting a closure operator which ensures that the abstract Kleene iterates are finitely many. This closure operator𝜌≤_A2 will be de-fined by using an ordering relation≤A2 induced by a FAA2such that𝐿2 = L(A2) and will be shown to be forward complete for the function𝜆 #»𝑿 . # »𝑳2𝐼1∩ gPre_A1( #»𝑿) used by FAIncGfp.

Forward completeness of abstract interpretations [Giacobazzi and Quintarelli 2001], also called exactness [Miné 2017, Definition 2.15], is different from and orthogonal to backward completeness introduced in Section 3 and crucially used throughout Sections 4–7. In particular, a remarkable con-sequence of exploiting a forward complete abstraction is that the Kleene iterates of the concrete and abstract greatest fixpoint computations coincide. The intuition here is that this forward com-plete closure𝜌≤_A2 allows us to establish that all the Kleene iterates of𝜆 #»𝑿 . # »𝑳2𝐼1∩ gPre_A1( #»𝑿) belong to the image of the closure𝜌≤_A2, more precisely that every Kleene iterate is a language which is upward closed for≤A2. Interestingly, a similar phenomenon occurs in well-structured transition systems [Abdulla et al. 1996; Finkel and Schnoebelen 2001].

Let us now describe in detail this abstraction. A closure𝜌 ∈ uco(𝐶) on a concrete domain 𝐶 is forward complete for a monotonic function𝑓 : 𝐶 → 𝐶 if 𝜌𝑓 𝜌 = 𝑓 𝜌 holds. The intuition here is that forward completeness means that no loss of precision is accumulated when the output of a computation of𝑓 𝜌 is approximated by 𝜌, or, equivalently, the concrete function 𝑓 maps abstract elements of𝜌 into abstract elements of 𝜌. Dually to the case of backward completeness, forward completeness implies that gfp(𝑓 ) = gfp(𝑓 𝜌) = gfp(𝜌𝑓 𝜌) holds, when these greatest fixpoints ex-ist (this is the case, e.g., when𝐶 is a complete lattice). When the function 𝑓 : 𝐶 → 𝐶 admits the right-adjoint e𝑓 : 𝐶 → 𝐶, i.e., 𝑓 (𝑐) ≤ 𝑐^′⇔ 𝑐 ≤ e𝑓 (𝑐^′) holds, it turns out that forward and backward completeness are related by the following duality [Giacobazzi and Quintarelli 2001, Corollary 1]:

𝜌 is backward complete for 𝑓 iff 𝜌 is forward complete for e𝑓 . (26) Thus, by (26), in the following result instead of assuming the hypotheses implying that a closure𝜌 is forward complete for the right-adjoint gPre_A1, we state some hypotheses which guarantee that 𝜌 is backward complete for its left-adjoint, that, by Lemma 8.2, is PreA1.

TheoRem 8.3. LetA1=⟨𝑄1, 𝛿1, 𝐼1, 𝐹1, Σ⟩ be a FA , 𝐿2be a regular language and𝜌 ∈ uco(℘(Σ^∗)).

Let us assume that:

(1) 𝜌(𝐿2) = 𝐿2;

(2) 𝜌 is backward complete for 𝜆𝑋 . 𝑎𝑋 for all 𝑎 ∈ Σ.

Then, L(A1) ⊆ 𝐿2 iff #»𝝐^𝐹1 ⊆ gfp(𝜆 #»𝑿 .𝜌( # »𝑳2𝐼1 ∩ gPre_A1(𝜌( #»𝑿)))). Moreover, the Kleene iterates of 𝜆 #»𝑿 . 𝜌( # »𝑳2𝐼1∩ gPre_A1(𝜌( #»𝑿))) and 𝜆 #»𝑿 . # »𝑳2𝐼1∩ gPre_A1( #»𝑿) from the initial value𝚺# »^∗coincide in lockstep.

PRoof. Theorem 4.3 shows that if𝜌 is backward complete for 𝜆𝑋 . 𝑎𝑋, for every 𝑎 ∈ Σ, then it is backward complete for Pre_A1. Thus, by (26),𝜌 is forward complete for gPre_A1. Then, it turns out that𝜌 is forward complete for 𝜆 #»𝑿 . # »𝑳2𝐼1∩ gPre_A1( #»𝑿), because:

𝜌( # »𝑳2𝐼1∩ gPre_A1(𝜌( #»𝑿))) = [by forward completeness for gPre_A1and𝜌(𝐿2) = 𝐿2] 𝜌(𝜌( # »𝑳2𝐼1) ∩ 𝜌(gPre_A1(𝜌( #»𝑿)))) = [by (3)]

𝜌( # »𝑳2𝐼1) ∩ 𝜌(gPre_A1(𝜌( #»𝑿))) = [by forward completeness for gPre_A1and𝜌(𝐿2) = 𝐿2] 𝑳# »2𝐼1∩ gPre_A1(𝜌( #»𝑿)) .

Since, by forward completeness, gfp(𝜆 #»𝑿 . # »𝑳2𝐼1∩ gPre_A1( #»𝑿)) = gfp(𝜆 #»𝑿 . 𝜌( # »𝑳2𝐼1∩ gPre_A1(𝜌( #»𝑿)))), by equivalence (25), we conclude thatL(A1) ⊆ 𝐿2iff #»𝝐^𝐹1 ⊆ gfp(𝜆 #»𝑿 . 𝜌( # »𝑳2𝐼1∩ gPre_A1(𝜌( #»𝑿)))).

Finally, we observe that the Kleene iterates of𝜆 #»𝑿 . # »𝑳2𝐼1∩gPre_A1( #»𝑿) and 𝜆 #»𝑿 . 𝜌( # »𝑳2𝐼1∩gPre_A1(𝜌( #»𝑿))) starting from𝚺# »^∗coincide in lockstep since𝜌( # »𝑳2𝐼1 ∩ gPre_A1(𝜌( #»𝑿))) = # »𝑳2𝐼1 ∩ gPre_A1(𝜌( #»𝑿)) and

𝜌( # »𝑳2𝐼1) = # »𝑳2𝐼1. □

We can now establish that the iterates of Kleene(⊇, 𝜆 #»𝑿 . # »𝑳2𝐼1∩ gPre_A1( #»𝑿),𝚺# »^∗) are finitely many.

Let𝐿2=L(A2), for some FA A2, and consider the corresponding left state-based quasiorder≤^𝑙_A2 onΣ^∗ as defined by (16). By Lemma 5.8,≤^𝑙_A2 is a left𝐿2-consistent wqo. Furthermore, since𝑄2

is finite, we have that both≤^𝑙_A

2 and (≤^𝑙_A

2)⁻¹ are wqos, so that, in turn, ⟨𝜌_≤𝑙

A2(℘(Σ^∗)), ⊆⟩ is a poset which is both ACC and DCC. In particular, the definition of≤^𝑙_A

2 implies that every chain in⟨𝜌_≤𝑙

A2(℘(Σ^∗)), ⊆⟩ has at most 2^|𝑄2|elements, so that if we compute 2^|𝑄2| Kleene iterates then we surely converge to the greatest fixpoint. Moreover, as a consequence of the DCC property, we have that Kleene(⊇, 𝜆 #»𝑿 . 𝜌≤_A2( # »𝑳2𝐼1∩ gPre_A1(𝜌≤_A2( #»𝑿))),𝚺# »^∗) always terminates, thus implying that Kleene(⊇, 𝜆 #»𝑿 . # »𝑳2𝐼1∩ gPre_A1( #»𝑿),𝚺# »^∗) terminates as well, because their iterates go in lockstep as stated by Theorem 8.3. We have therefore shown the correctness of FAIncGfp.

CoRollaRy 8.4. The algorithm FAIncGfp decides the inclusionL(A1) ⊆ 𝐿2

Example 8.5. Let us illustrate the greatest fixpoint algorithm FAIncGfp on the inclusion check 𝐿(B) ⊆ 𝐿(A) where A is the FA in Fig. 1 and B is the following FA:

𝑞3 𝑞4

𝑏

𝑎 𝑎

By Corollary 8.4, the Kleene iterates of𝜆 #»𝒀 .𝑳(A)# »^{𝑞3} ∩ gPre_B( #»𝒀 ) are guaranteed to converge in finitely many steps. We have that

# »

𝑳(A)^{𝑞3}∩ gPre_B(⟨𝑌3, 𝑌4⟩) = ⟨𝐿(A) ∩ 𝑎⁻¹𝑌4, 𝑏⁻¹𝑌3∩ 𝑎⁻¹𝑌4⟩ .

Then, the Kleene iterates are as follows (we automatically checked them by the FAdo tool [Almeida et al. 2009]):

𝑌₃⁽⁰⁾=Σ^∗ 𝑌₄⁽⁰⁾=Σ^∗

𝑌₃⁽¹⁾=𝐿(A) ∩ 𝑎⁻¹Σ^∗=𝐿(A) 𝑌₄⁽¹⁾=𝑏⁻¹Σ^∗∩ 𝑎⁻¹Σ^∗=Σ^∗

𝑌₃⁽²⁾=𝐿(A) ∩ 𝑎⁻¹Σ^∗=𝐿(A) 𝑌₄⁽²⁾=𝑏⁻¹𝐿(A) ∩ 𝑎⁻¹Σ^∗=𝑏⁻¹𝐿(A) = (𝑏^∗𝑎)⁺ 𝑌₃⁽³⁾=𝐿(A) ∩ 𝑎⁻¹(𝑏^∗𝑎)⁺ =𝐿(A) 𝑌₄⁽³⁾=𝑏⁻¹𝐿(A) ∩ 𝑎⁻¹(𝑏^∗𝑎)⁺=(𝑏^∗𝑎)⁺

Thus, Kleene outputs the vector⟨𝑌3, 𝑌4⟩ = ⟨𝐿(A), (𝑏^∗𝑎)⁺⟩. Since 𝜖 ∈ 𝐿(A), FAIncGfp concludes

that𝐿(B) ⊆ 𝐿(A) holds. ^

Finally, it is worth citing that Fiedor et al. [2019] put forward an algorithm for deciding WS1S formulae which relies on the same lfp computation used in FAIncS. Then, they derive a dual gfp computation by relying on Park’s duality [Park 1969]: lfp(𝜆𝑋 . 𝑓 (𝑋)) = (gfp(𝜆𝑋 . (𝑓 (𝑋^𝑐))^𝑐))^𝑐. Their approach differs from ours since we use the equivalence (24) to compute a gfp, different from the lfp, which still allows us to decide the inclusion problem. Furthermore, their algorithm decides whether a given automaton accepts𝜖 and it is not clear how their algorithm could be extended for deciding language inclusion.