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.