Antichains as a Galois Connection

Nel documento 1 Complete Abstractions for Checking Language Inclusion (pagine 22-27)

6 A NOVEL PERSPECTIVE ON THE ANTICHAIN ALGORITHM

6.2 Antichains as a Galois Connection

LetA1=βŸ¨π‘„1, 𝛿1, 𝐼1, 𝐹1, Σ⟩ and A2=βŸ¨π‘„2, 𝛿2, 𝐼2, 𝐹2, Σ⟩ be two FAs and consider the state-based left L(A2)-consistent wqo ⩽𝑙A

2 defined by (16). Theorem 5.3 shows that Algorithm FAIncW decides L(A1) βŠ† L(A2) by computing vectors of finite sets of words. Since 𝑒 ⩽𝑙A2 𝑣 ⇔ pre𝑒A2(𝐹2) βŠ† preA𝑣2(𝐹2), we can equivalently consider the set of states pre𝑒A2(𝐹2) ∈ β„˜(𝑄2) rather than a word 𝑒 ∈ Ξ£βˆ—. This observation suggests to design a version of Algorithm FAIncW that computes Kleene it-erates on the poset⟨ACβŸ¨β„˜(𝑄2),βŠ†βŸ©, βŠ‘βŸ© of antichains of sets of states of the complete lattice βŸ¨β„˜(𝑄2), βŠ†βŸ©.

To achieve this, ⟨ACβŸ¨β„˜(𝑄2),βŠ†βŸ©, βŠ‘βŸ© is viewed as an abstract domain through the following maps 𝛼 : β„˜(Ξ£βˆ—) β†’ ACβŸ¨β„˜(𝑄2),βŠ†βŸ© and𝛾 : ACβŸ¨β„˜(𝑄2),βŠ†βŸ© β†’ β„˜(Ξ£βˆ—). Moreover, we use the abstract function PreAA2

1:(ACβŸ¨β„˜(𝑄2),βŠ†βŸ©)|𝑄1| β†’ (ACβŸ¨β„˜(𝑄2),βŠ†βŸ©)|𝑄1|defined as follows:

𝛼 (𝑋) β‰œ ⌊{pre𝑒A2(𝐹2) ∈ β„˜(𝑄2) | 𝑒 ∈ 𝑋 }βŒ‹ ,

𝛾 (π‘Œ) β‰œ {𝑣 ∈ Ξ£βˆ—| βˆƒπ‘¦ ∈ π‘Œ, 𝑦 βŠ† pre𝑣A2(𝐹2)} , (21)

PreAA2

1(βŸ¨π‘‹π‘žβŸ©π‘žβˆˆπ‘„1) β‰œ ⟨⌊{preπ‘ŽA2(𝑆) ∈ β„˜(𝑄2) | βˆƒπ‘Ž ∈ Ξ£, π‘žβ€²βˆˆ 𝑄1, π‘žβ€²βˆˆ 𝛿1(π‘ž, π‘Ž) ∧ 𝑆 ∈ π‘‹π‘žβ€²}βŒ‹βŸ©π‘žβˆˆπ‘„1, where βŒŠπ‘‹βŒ‹ is the unique minor set w.r.t. subset inclusion of 𝑋 βŠ† β„˜(𝑄2). Observe that the func-tions𝛼 and PreAA2

1are well-defined because minors of finite subsets ofβ„˜(𝑄2) are uniquely defined antichains.

Lemma 6.2. The following properties hold:

(a) βŸ¨β„˜(Ξ£βˆ—), βŠ†βŸ© βˆ’βˆ’βˆ’β†’β†βˆ’βˆ’βˆ’

𝛼

𝛾 ⟨ACβŸ¨β„˜(𝑄2),βŠ†βŸ©, βŠ‘βŸ© is a GC;

(b)𝛾 ◦𝛼 = πœŒβ©½π‘™

A2; (c) PreAA2

1=𝛼◦PreA1 ◦𝛾.

PRoof.

(a) Let us first observe that𝛼 is well-defined: 𝛼 (𝑋) is an antichain of βŸ¨β„˜(𝑄2), βŠ†βŸ© since it is a minor for the well-quasiorderβŠ† and, therefore, it is finite. Then, for all 𝑋 ∈ β„˜(Ξ£βˆ—) andπ‘Œ ∈ ACβŸ¨β„˜(𝑄2),βŠ†βŸ©, it turns out that:

𝛼 (𝑋) βŠ‘ π‘Œ ⇔ [by definition ofβŠ‘]

βˆ€π‘§ ∈ 𝛼 (𝑋), βˆƒπ‘¦ ∈ π‘Œ, 𝑦 βŠ† 𝑧 ⇔ [by definition of𝛼]

βˆ€π‘§ ∈ ⌊{pre𝑒A2(𝐹2) ∈ β„˜(𝑄2) | 𝑒 ∈ 𝑋 }βŒ‹, βˆƒπ‘¦ ∈ π‘Œ, 𝑦 βŠ† 𝑧 ⇔ [by definition ofβŒŠΒ·βŒ‹]

βˆ€π‘’ ∈ 𝑋, βˆƒπ‘¦ ∈ π‘Œ, 𝑦 βŠ† pre𝑒A2(𝐹2) ⇔ [by definition of𝛾]

𝑋 βŠ† 𝛾 (π‘Œ) . (b) For all𝑋 ∈ β„˜(Ξ£βˆ—):

𝛾 (𝛼 (𝑋)) = [by definition of𝛼,𝛾]

{𝑣 ∈ Ξ£βˆ— | βˆƒπ‘’ ∈ Ξ£βˆ—, pre𝑒A2(𝐹2) ∈ ⌊{preA𝑀2(𝐹2) | 𝑀 ∈ 𝑋 }βŒ‹ ∧ pre𝑒A2(𝐹2) βŠ† pre𝑣A2(𝐹2)}

= [by definition of minor]

{𝑣 ∈ Ξ£βˆ— | βˆƒπ‘’ ∈ 𝑋, pre𝑒A2(𝐹2) βŠ† pre𝑣A2(𝐹2)} = [by definition of⩽𝑙A2] {𝑣 ∈ Ξ£βˆ—| βˆƒπ‘’ ∈ 𝑋, 𝑒 ⩽𝑙A2𝑣} = [by definition ofπœŒβ©½π‘™

A2] πœŒβ©½π‘™

A2(𝑋) . (c) For all #»𝑿 ∈ (ACβŸ¨β„˜(𝑄2),βŠ†βŸ©)|𝑄1|:

𝛼 (PreA1(𝛾 ( #»𝑿))) =

[by definition of PreA1]

βŸ¨π›Ό (Ð

π‘ŽβˆˆΞ£,π‘žβ†’π‘ŽA1π‘žβ€²π‘Žπ›Ύ ( #Β»π‘Ώπ‘žβ€²))βŸ©π‘žβˆˆπ‘„1=

[by definition of𝛼]

⟨⌊{pre𝑒A2(𝐹2) | 𝑒 ∈Ð

π‘ŽβˆˆΞ£,π‘žβ†’π‘ŽA1π‘žβ€²π‘Žπ›Ύ ( #Β»π‘Ώπ‘žβ€²)βŒ‹βŸ©π‘žβˆˆπ‘„1=

[by preπ‘Žπ‘£A2=preπ‘ŽA2β—¦preA𝑣2]

⟨⌊{preπ‘ŽA2({preA𝑣2(𝐹2) | 𝑣 ∈Ð

π‘žβ†’π‘ŽA1π‘žβ€²π›Ύ ( #Β»π‘Ώπ‘žβ€²)}) | π‘Ž ∈ Ξ£}βŒ‹βŸ©π‘žβˆˆπ‘„1=

[by rewriting]

⟨⌊{preπ‘ŽA2(𝑆) | π‘Ž ∈ Ξ£, π‘žβ†’π‘ŽA1π‘žβ€², 𝑆 ∈ {pre𝑣A2(𝐹2) | 𝑣 ∈ 𝛾 ( #Β»π‘Ώπ‘žβ€²)}}βŒ‹βŸ©π‘žβˆˆπ‘„1=

[by⌊{preπ‘ŽA2(𝑆) | 𝑆 ∈ π‘Œ }βŒ‹ = ⌊{preπ‘ŽA2(𝑆) | 𝑆 ∈ βŒŠπ‘ŒβŒ‹}βŒ‹]

⟨⌊{preπ‘ŽA2(𝑆) | π‘Ž ∈ Ξ£, π‘žβ†’π‘Ž A1π‘žβ€², 𝑆 ∈ ⌊{pre𝑣A2(𝐹2) | 𝑣 ∈ 𝛾 ( #Β»π‘Ώπ‘žβ€²)}βŒ‹}βŒ‹βŸ©π‘žβˆˆπ‘„1=

[by definition of𝛼]

⟨⌊{preπ‘ŽA2(𝑆) | π‘Ž ∈ Ξ£, π‘žβ†’π‘ŽA1π‘žβ€², 𝑆 ∈ 𝛼 (𝛾 ( #Β»π‘Ώπ‘žβ€²))βŒ‹βŸ©π‘žβˆˆπ‘„1=

[since #»𝑿 ∈ 𝛼, 𝛼 (𝛾 ( #Β»π‘Ώπ‘žβ€²)) = #Β»π‘Ώπ‘žβ€²]

⟨⌊{preπ‘ŽA2(𝑆) | π‘Ž ∈ Ξ£, π‘žβ†’π‘Ž A1π‘žβ€², 𝑆 ∈ #Β»π‘Ώπ‘žβ€²}βŒ‹βŸ©π‘žβˆˆπ‘„1=

[by definition of PreAA2

1] PreAA2

1( #»𝑿) . β–‘

Thus, by Lemmata 5.8 and 6.2, it turns out that the GCβŸ¨β„˜(Ξ£βˆ—), βŠ†βŸ© βˆ’βˆ’βˆ’β†’β†βˆ’βˆ’βˆ’

𝛼

𝛾 ⟨ACβŸ¨β„˜(𝑄2),βŠ†βŸ©, βŠ‘βŸ© and the abstract function PreAA2

1 satisfy the hypotheses (i)-(iv) of Theorem 6.1. To obtain an algorithm for decidingL(A1) βŠ† L(A2), it remains to show that the hypothesis (v) of Theorem 6.1 holds, i.e., there is an algorithm to decide whether #»𝒀 βŠ‘ 𝛼 ( # »𝑳2𝐼2) for every #»𝒀 ∈ 𝛼 (β„˜(Ξ£βˆ—))|𝑄1|.

Notice that the Kleene iterates ofπœ† #»𝑿♯. 𝛼 ( #»𝝐𝐹1) βŠ” PreAA2

1( #»𝑿♯) of Theorem 6.1 are vectors of an-tichains in⟨ACβŸ¨β„˜(𝑄2),βŠ†βŸ©, βŠ‘βŸ©, where each component is indexed by some π‘ž ∈ 𝑄1and represents, through its minor, a set of sets of states that are predecessors of𝐹2inA2through a word𝑒 gen-erated byA1from that stateπ‘ž, i.e., pre𝑒A2(𝐹2) with 𝑒 ∈ π‘Šπ‘ž,𝐹A11. Sinceπœ– ∈ π‘Šπ‘ž,𝐹A11 for allπ‘ž ∈ 𝐹1and preπœ–A2(𝐹2) = 𝐹2, the first iteration of Kleene gives the vector𝛼 ( #»𝝐𝐹1) = βŸ¨πœ“βˆ…πΉ2(π‘ž ∈?𝐹1)βŸ©π‘žβˆˆπ‘„1. Let us also observe that by taking the minor of each vector component, we are considering smaller sets which still preserve the relationβŠ‘ since the following equivalences hold:

𝐴 βŠ‘ 𝐡 ⇔ βŒŠπ΄βŒ‹ βŠ‘ 𝐡 ⇔ 𝐴 βŠ‘ βŒŠπ΅βŒ‹ ⇔ βŒŠπ΄βŒ‹ βŠ‘ βŒŠπ΅βŒ‹.

LetβŸ¨π‘Œπ‘žβŸ©π‘žβˆˆπ‘„1be the output of Kleene(βŠ‘, πœ† #»𝑿♯. 𝛼 ( #»𝝐𝐹1) βŠ” PreAA21( #»𝑿♯), #Β»βˆ…βˆ…βˆ…). Hence, we have that, for each componentπ‘ž ∈ 𝑄1,π‘Œπ‘ž =⌊{pre𝑒A2(𝐹2) | 𝑒 ∈ π‘Šπ‘ž,𝐹A11}βŒ‹ holds. Whenever the inclusion L(A1) βŠ† L(A2) holds, all the sets of states in π‘Œπ‘ž, for some initial stateπ‘ž ∈ 𝐼1, are predecessors of𝐹2inA2

through words inL(A2), so that for each π‘ž ∈ 𝐼1and𝑆 ∈ π‘Œπ‘ž,𝑆 ∩ 𝐼2β‰ βˆ… must hold. As a result, the following state-based algorithm FAIncS (S stands for state) decides the inclusionL(A1) βŠ† L(A2) by computing on the abstract domain of antichains⟨ACβŸ¨β„˜(𝑄2),βŠ†βŸ©, βŠ‘βŸ©.

FAIncS: State-based algorithm forL(A1) βŠ† L(A2) Data: FAsA1=βŸ¨π‘„1, 𝛿1, 𝐼1, 𝐹1, Σ⟩ and A2=βŸ¨π‘„2, 𝛿2, 𝐼2, 𝐹2, Σ⟩.

1 βŸ¨π‘Œπ‘žβŸ©π‘žβˆˆπ‘„1:=Kleene(βŠ‘, πœ† #»𝑿♯. 𝛼 ( #»𝝐𝐹1) βŠ” PreAA2

1( #»𝑿♯), #Β»βˆ…βˆ…βˆ…);

2 forallπ‘ž ∈ 𝐼1do

3 forall𝑆 ∈ π‘Œπ‘ždo

4 if𝑆 ∩ 𝐼2=βˆ… then return false;

5 return true;

TheoRem 6.3. The algorithm FAIncS decides the inclusion problemL(A1) βŠ† L(A2).

PRoof. We show that all the hypotheses (i)-(v) of Theorem 6.1 are satisfied for the abstract domain⟨𝐷, β‰€π·βŸ© = ⟨ACβŸ¨β„˜(𝑄2),βŠ†βŸ©, βŠ‘βŸ© as defined by the GC of Lemma 6.2.

(i) SinceπœŒβ‰€π‘™

A2(𝑋) = 𝛾 (𝛼 (𝑋)), it follows from Lemmata 5.2 and 5.8 that 𝐿2 ∈ 𝛾 (𝐷). Moreover, by Lemma 5.2 (b) withπœŒβ‰€π‘™

A2 = 𝛾𝛼, we have that for all π‘Ž ∈ Ξ£, 𝑋 ∈ β„˜(Ξ£βˆ—), 𝛾 (𝛼 (π‘Žπ‘‹)) = 𝛾 (𝛼 (π‘Žπ›Ύ (𝛼 (𝑋)))).

(ii) ⟨ACβŸ¨β„˜(𝑄2),βŠ†βŸ©, βŠ‘, βŠ”, βˆ…βŸ© is an effective domain because 𝑄2is finite.

(iii) By Lemma 6.2 (c), we have that𝛼 (PreA1(𝛾 ( #»𝑿♯))) = PreAA21( #»𝑿♯), for all #»𝑿♯ ∈ 𝛼 (β„˜(Ξ£βˆ—))|𝑄1|, and PreAA2

1is computable.

(iv) 𝛼 ({πœ–}) = {𝐹2} and 𝛼 (βˆ…) = βˆ…, hence 𝛼 ( #»𝝐𝐹1) is trivial to compute.

(v) Since 𝛼 ( # »𝑳2𝐼1) = βŸ¨π›Ό (πœ“πΏΞ£βˆ—2(π‘ž ∈?𝐼1))βŸ©π‘žβˆˆπ‘„1, for all #»𝒀 ∈ 𝛼 (β„˜(Ξ£βˆ—))|𝑄1|, the relation βŸ¨π‘Œπ‘žβŸ©π‘žβˆˆπ‘„1 βŠ‘ 𝛼 ( # »𝑳2𝐼1) trivially holds for all components π‘ž βˆ‰ 𝐼1, since𝛼 (Ξ£βˆ—) is the greatest antichain. For the componentsπ‘ž ∈ 𝐼1, it suffices to show thatπ‘Œπ‘ž βŠ‘ 𝛼 (𝐿2) ⇔ βˆ€π‘† ∈ π‘Œπ‘ž, 𝑆 ∩ 𝐼2 β‰ βˆ…, which is the check performed by lines 2-5 of algorithm FAIncS:

π‘Œπ‘žβŠ‘ 𝛼 (𝐿2) ⇔ [becauseπ‘Œπ‘ž=𝛼 (π‘ˆ ) for some π‘ˆ ∈ β„˜(Ξ£βˆ—)]

𝛼 (π‘ˆ ) βŠ‘ 𝛼 (𝐿2) ⇔ [by GC]

π‘ˆ βŠ† 𝛾 (𝛼 (𝐿2)) ⇔ [by (i),𝛾 (𝛼 (𝐿2)) = 𝐿2] π‘ˆ βŠ† 𝐿2⇔ [by definition of pre𝑒A2]

βˆ€π‘’ ∈ π‘ˆ, pre𝑒A2(𝐹2) ∩ 𝐼2β‰ βˆ… ⇔ [becauseπ‘Œπ‘ž=𝛼 (π‘ˆ ) = ⌊{pre𝑒A2(𝐹2) | 𝑒 ∈ π‘ˆ }βŒ‹]

βˆ€π‘† ∈ π‘Œπ‘ž, 𝑆 ∩ 𝐼2β‰ βˆ… .

Thus, by Theorem 6.1, the algorithm FAIncS solves the inclusion problemL(A1) βŠ† L(A2). β–‘ 6.3 Relationship to the Antichain Algorithm

De Wulf et al. [2006] introduced two so-called antichain algorithms, called forward and backward, for deciding the universality of the language accepted by a FA, i.e., whether the language isΞ£βˆ— or not. Then, they extended the backward algorithm in order to decide inclusion of languages

accepted by FAs. In what follows, we show that our algorithm FAIncS is equivalent to the cor-responding extension of the forward antichain algorithm and, therefore, dual to the backward antichain algorithm for language inclusion put forward by De Wulf et al. [2006, Theorem 6]. To achieve this, we first define the poset of antichains in which the forward antichain algorithm computes its fixpoint. Then, we give a formal definition of the forward antichain algorithm for deciding language inclusion and show that this algorithm coincides with FAIncS when applied to the reverse automata. Since language inclusion between the languages generated by two FAs holds iff inclusion holds between the languages generated by their reverse FAs, this entails that our algorithm FAIncS is equivalent to the forward antichain algorithm.

Consider a language inclusion problemL(A1) βŠ† L(A2) with A1=βŸ¨π‘„1, 𝛿1, 𝐼1, 𝐹1, Σ⟩ and A2=

βŸ¨π‘„2, 𝛿2, 𝐼2, 𝐹2, Σ⟩. Let us consider the following poset of antichains ⟨ACβŸ¨β„˜(𝑄2),βŠ†βŸ©, eβŠ‘βŸ© where 𝑋 eβŠ‘ π‘Œ ⇐⇒ βˆ€π‘¦ ∈ π‘Œ, βˆƒπ‘₯ ∈ 𝑋, π‘₯ βŠ† 𝑦△

and notice that eβŠ‘ coincides with the reverse βŠ‘βˆ’1of the relation defined by (1). As observed by De Wulf et al. [2006, Lemma 1], it turns out that⟨ACβŸ¨β„˜(𝑄2),βŠ†βŸ©, eβŠ‘, eβŠ”, eβŠ“, {βˆ…}, βˆ…βŸ© is a finite lattice, where eβŠ” and eβŠ“ denote, resp., lub and glb, and {βˆ…} and βˆ… are, resp., the least and greatest elements. This lattice⟨ACβŸ¨β„˜(𝑄2),βŠ†βŸ©, eβŠ‘βŸ© is the domain in which the forward antichain algorithm computes on for deciding language universality [De Wulf et al. 2006, Theorem 3]. The following result extends this forward algorithm in order to decide language inclusion.

TheoRem 6.4 ([De Wulf et al. 2006, THeoRems 3 and 6]). Let

# Β»

FP β‰œ eΓƒ{ #»𝑿 ∈ (ACβŸ¨β„˜(𝑄2),βŠ†βŸ©)|𝑄1| | #»𝑿 = PostAA2

1( #»𝑿) eβŠ“ βŸ¨πœ“βˆ…{𝐼2}(π‘ž ∈?𝐼1)βŸ©π‘žβˆˆπ‘„1} where PostAA2

1(βŸ¨π‘‹π‘žβŸ©π‘žβˆˆπ‘„1) β‰œ ⟨⌊{postπ‘ŽA2(𝑆) ∈ β„˜(𝑄2) | βˆƒπ‘Ž ∈ Ξ£, π‘žβ€²βˆˆ 𝑄1, π‘ž ∈ 𝛿1(π‘žβ€², π‘Ž) ∧ 𝑆 ∈ π‘‹π‘žβ€²}βŒ‹βŸ©π‘žβˆˆπ‘„1. Then,L(A1) ⊈ L(A2) if and only if there exists π‘ž ∈ 𝐹1such that # Β»FPπ‘ž eβŠ‘ {𝐹𝑐2}.

PRoof. Let us first introduce some notation to describe the forward antichain algorithm by De Wulf et. al [2006] which decides L(A1) βŠ† L(A2). Let us consider the poset βŸ¨π‘„1Γ— β„˜(𝑄2), βŠ†Γ—βŸ© where (π‘ž1, 𝑆1) βŠ†Γ— (π‘ž2, 𝑆2) ⇔ π‘žβ–³ 1 =π‘ž2∧ 𝑆1 βŠ† 𝑆2. Then, let⟨ACβŸ¨π‘„1Γ—β„˜(𝑄2),βŠ†Γ—βŸ©, eβŠ‘Γ—, eβŠ”Γ—, eβŠ“Γ—βŸ© be the lattice of antichains overβŸ¨π‘„1Γ— β„˜(𝑄2), βŠ†Γ—βŸ© where:

𝑋 eβŠ‘Γ—π‘Œ ⇔ βˆ€(π‘ž,𝑇 ) ∈ π‘Œ, βˆƒ(π‘ž, 𝑆) ∈ 𝑋, 𝑆 βŠ† 𝑇△

𝑋 eβŠ”Γ—π‘Œ β‰œ minΓ—({(π‘ž, 𝑆 βˆͺ 𝑇 ) | (π‘ž, 𝑆) ∈ 𝑋, (π‘ž,𝑇 ) ∈ π‘Œ }) 𝑋 eβŠ“Γ—π‘Œ β‰œ minΓ—({(π‘ž, 𝑆) | (π‘ž, 𝑆) ∈ 𝑋 βˆͺ π‘Œ })

with minΓ—(𝑋) β‰œ {(π‘ž, 𝑆) ∈ 𝑋 | βˆ€(π‘žβ€², 𝑆′) ∈ 𝑋, π‘ž = π‘žβ€²β‡’ π‘†β€²βŠ„π‘†} . Also, let Post : ACβŸ¨π‘„1Γ—β„˜(𝑄2),βŠ†Γ—βŸ©β†’ ACβŸ¨π‘„1Γ—β„˜(𝑄2),βŠ†Γ—βŸ©be defined as follows:

Post(𝑋) β‰œ minΓ—({(π‘ž, postπ‘ŽA2(𝑆)) ∈ 𝑄1Γ— β„˜(𝑄2) | βˆƒπ‘Ž ∈ Ξ£, π‘ž ∈ 𝑄1, (π‘žβ€², 𝑆) ∈ 𝑋, π‘žβ€² π‘Žβ†’A1π‘ž}) . Then, the dual of the backward antichain algorithm in [De Wulf et al. 2006, Theorem 6] states that L(A1) ⊈ L(A2) iff there exists π‘ž ∈ 𝐹1such thatF P eβŠ‘Γ—{(π‘ž, 𝐹2𝑐)} where

F P = eÃ

Γ—{𝑋 ∈ ACβŸ¨π‘„1Γ—β„˜(𝑄2),βŠ†Γ—βŸ© | 𝑋 = Post(𝑋) eβŠ“Γ— (𝐼1Γ— {𝐼2})} .

We observe that for some𝑋 ∈ ACβŸ¨π‘„1Γ—β„˜(𝑄2),βŠ†Γ—βŸ©, a pair (π‘ž, 𝑆) ∈ 𝑄1Γ— β„˜(𝑄2) such that (π‘ž, 𝑆) ∈ 𝑋 is used by [De Wulf et al. 2006, Theorem 6] simply as a way to associate statesπ‘ž of A1 with sets𝑆 of states of A2. In fact, an antichain𝑋 ∈ ACβŸ¨π‘„1Γ—β„˜(𝑄2),βŠ†Γ—βŸ© can be equivalently formalized by a vector⟨{𝑆 ∈ β„˜(𝑄2) | (π‘ž, 𝑆) ∈ 𝑋 }βŸ©π‘žβˆˆπ‘„1 ∈ (ACβŸ¨β„˜(𝑄2),βŠ†βŸ©)|𝑄1|whose components are indexed by

statesπ‘ž ∈ 𝑄1and are antichains of sets of states in ACβŸ¨β„˜(𝑄2),βŠ†βŸ©. Correspondingly, we consider the lattice⟨ACβŸ¨β„˜(𝑄2),βŠ†βŸ©, eβŠ‘βŸ©, where for all 𝑋, π‘Œ ∈ ACβŸ¨β„˜(𝑄2),βŠ†βŸ©:

𝑋 eβŠ‘ π‘Œ ⇔ βˆ€π‘‡ ∈ π‘Œ, βˆƒπ‘† ∈ 𝑋, 𝑆 βŠ† 𝑇△

𝑋 eβŠ”π‘Œ β‰œ min({𝑆 βˆͺ 𝑇 ∈ β„˜(𝑄2) | 𝑆 ∈ 𝑋,𝑇 ∈ π‘Œ }) 𝑋 eβŠ“π‘Œ β‰œ min({𝑆 ∈ β„˜(𝑄2) | 𝑆 ∈ 𝑋 βˆͺ π‘Œ }) with min(𝑋) β‰œ {𝑆 ∈ 𝑋 | βˆ€π‘†β€²βˆˆ 𝑋, π‘†β€²βŠ„π‘†} . Then, these definitions allow us to replace Post by an equivalent function

PostAA2

1:(ACβŸ¨β„˜(𝑄2),βŠ†βŸ©)|𝑄1| β†’ (ACβŸ¨β„˜(𝑄2),βŠ†βŸ©)|𝑄1| that transforms vectors of antichains as follows:

PostAA2

1(βŸ¨π‘‹π‘žβŸ©π‘žβˆˆπ‘„1) β‰œ ⟨min({postπ‘ŽA2(𝑆) ∈ β„˜(𝑄2) | βˆƒπ‘Ž ∈ Ξ£, π‘žβ€²βˆˆ 𝑄1, 𝑆 ∈ π‘‹π‘žβ€², π‘žβ€² π‘Žβ†’A1π‘ž})βŸ©π‘žβˆˆπ‘„1 . In turn, the aboveF P ∈ ACβŸ¨π‘„1Γ—β„˜(𝑄2),βŠ†Γ—βŸ©is replaced by the following equivalent vector:

# Β»

FP β‰œ eΓƒ{ #»𝑿 ∈ (ACβŸ¨β„˜(𝑄2),βŠ†βŸ©)|𝑄1| | #»𝑿 = PostAA2

1( #»𝑿) eβŠ“ βŸ¨πœ“βˆ…{𝐼2}(π‘ž ∈?𝐼1)βŸ©π‘žβˆˆπ‘„1} .

Finally, the conditionβˆƒπ‘ž ∈ 𝐹1, F P eβŠ‘Γ—{(π‘ž, 𝐹2𝑐)} is equivalent to βˆƒπ‘ž ∈ 𝐹1,FP# Β»π‘ž eβŠ‘ {𝐹2𝑐}. β–‘ Let us recall thatA𝑅denotes the reverse automaton of A, where arrows are flipped and the initial/final states become final/initial. Note that language inclusion can be decided by considering the reverse automata sinceL(A1) βŠ† L(A2) ⇔ L(A𝑅1) βŠ† L(A2𝑅) holds. Furthermore, let us observe that PostAA2

1 =PreAA𝑅2𝑅

1

. We therefore obtain the following consequence of Theorem 6.4.

CoRollaRy 6.5. Let

# Β» FP β‰œ eΓƒ

{ #»𝑿 ∈ (ACβŸ¨β„˜(𝑄2),βŠ†βŸ©)|𝑄1| | #»𝑿 = PreAA21( #»𝑿) eβŠ“ βŸ¨πœ“βˆ…{𝐹2}(π‘ž ∈? 𝐹1)βŸ©π‘žβˆˆπ‘„1} . Then,L(A1) ⊈ L(A2) iff βˆƒπ‘ž ∈ 𝐼1,FP# Β»π‘ž eβŠ‘ {𝐼2𝑐}.

Since eβŠ‘ = βŠ‘βˆ’1, we have thateβŠ“ = βŠ”, eβŠ” = βŠ“ and the greatest element βˆ… for eβŠ‘ is the least element forβŠ‘. Moreover, by (21), 𝛼 ( #»𝝐𝐹1) = βŸ¨πœ“βˆ…{𝐹2}(π‘ž ∈?𝐹1)βŸ©π‘žβˆˆπ‘„1. Therefore, we can rewrite the vector # Β»FP of Corollary 6.5 as

# Β» FP =d

{ #»𝑿 ∈ (ACβŸ¨β„˜(𝑄2),βŠ†βŸ©)|𝑄1| | #»𝑿 = PreAA2

1( #»𝑿) βŠ” 𝛼 ( #»𝝐𝐹1)} , which is precisely the least fixpoint in ⟨(ACβŸ¨β„˜(𝑄2),βŠ†βŸ©)|𝑄1|, βŠ‘βŸ© of PreAA2

1 above𝛼 ( #»𝝐𝐹1). Hence, it turns out that the Kleene iterates of the least fixpoint computation that converge to # Β»FP exactly coincide with the iterates computed by the Kleene procedure of the state-based algorithm FAIncS.

In particular, if #»𝒀 is the output vector of Kleene(βŠ‘, πœ† #»𝑿 . 𝛼 ( #»𝝐𝐹1) βŠ”PreAA2

1( #»𝑿), #Β»βˆ…βˆ…βˆ…) at line 1 of FAIncS then #»𝒀 =FP. Furthermore, βˆƒπ‘ž ∈ 𝐼# Β» 1,FP# Β»π‘ž eβŠ‘ {𝐼2𝑐} ⇔ βˆƒπ‘ž ∈ 𝐼1, βˆƒπ‘† ∈FP# Β»π‘ž, 𝑆 ∩ 𝐼2 =βˆ…. Summing up, theβŠ‘-lfp algorithm FAIncS exactly coincides with the eβŠ‘-gfp antichain algorithm as given by Corollary 6.5.

We can easily derive an antichain algorithm which is perfectly equivalent to FAIncS by con-sidering the antichain lattice⟨ACβŸ¨β„˜(𝑄2),βŠ‡βŸ©, βŠ‘βŸ© for the dual lattice βŸ¨β„˜(𝑄2), βŠ‡βŸ© and by replacing the functions𝛼, 𝛾 and PreAA21of Lemma 6.2, resp., with the following dual versions:

𝛼𝑐(𝑋) β‰œ ⌊{cpre𝑒A2(𝐹𝑐2) ∈ β„˜(𝑄2) | 𝑒 ∈ 𝑋 }βŒ‹ , 𝛾𝑐(π‘Œ ) β‰œ {𝑣 ∈ Ξ£βˆ— | βˆƒπ‘¦ ∈ π‘Œ,𝑦 βŠ‡ cpreA𝑣2(𝐹2𝑐)} , CPreAA2

1(βŸ¨π‘‹π‘žβŸ©π‘žβˆˆπ‘„1) β‰œ ⟨⌊{cpreπ‘ŽA2(𝑆) ∈ β„˜(𝑄2) | βˆƒπ‘Ž ∈ Ξ£, π‘žβ€²βˆˆ 𝑄1, π‘žβ€²βˆˆ 𝛿1(π‘ž, π‘Ž) ∧ 𝑆 ∈ π‘‹π‘žβ€²}βŒ‹βŸ©π‘žβˆˆπ‘„1,

where cpre𝑒A2(𝑆) β‰œ (pre𝑒A2(𝑆𝑐))𝑐for𝑒 ∈ Ξ£βˆ—. When using these functions, the corresponding al-gorithm computes on the abstract domain⟨ACβŸ¨β„˜(𝑄2),βŠ‡βŸ©, βŠ‘βŸ© and it turns out that L(A1) βŠ† L(A2) iff Kleene(βŠ‘, πœ† #»𝑿♯. 𝛼𝑐( #»𝝐𝐹1) βŠ” CPreAA2

1( #»𝑿♯), #Β»βˆ…βˆ…βˆ…) βŠ‘ 𝛼𝑐( # »𝑳2𝐼1). This language inclusion algorithm co-incides with the backward antichain algorithm defined by De Wulf et al. [2006, Theorem 6] since both compute on the same lattice,βŒŠπ‘‹βŒ‹ corresponds to the maximal (w.r.t. set inclusion) elements of𝑋, 𝛼𝑐({πœ–}) = {𝐹2𝑐} and for all 𝑋 ∈ 𝛼𝑐(β„˜(Ξ£βˆ—)), we have that 𝑋 βŠ‘ 𝛼𝑐(𝐿2) ⇔ βˆ€π‘† ∈ 𝑋, 𝐼2⊈ 𝑆.

We have thus shown that the two forward/backward antichain algorithms introduced by De Wulf et al. [2006] can be systematically derived by instantiating our framework. The original an-tichain algorithms were later improved by Abdulla et al. [2010] and, subsequently, by Bonchi and Pous [2013]. Among their improvements, they showed how to exploit a precomputed binary rela-tion between pairs of states of the input automata such that language inclusion holds for all the pairs in the relation. When that binary relation is a simulation relation, our framework allows to partially match their results by using the simulation-based quasiorderβͺ―π‘ŸA defined in Section 5.3.2.

However, this relationβͺ―π‘ŸA does not consider pairs of states𝑄2Γ— 𝑄2whereas the aforementioned algorithms do.

Nel documento 1 Complete Abstractions for Checking Language Inclusion (pagine 22-27)