Abstract Dialectical Frameworks are Boolean Networks⋆ Jesse Heyninck1,2 , Matthias Knorr3 and JoΓ£o Leite3 1 Open Universiteit, the Netherlands 2 University of Cape Town, South-Africa 3 NOVA LINCS, NOVA University Lisbon Abstract Abstract dialectical frameworks are a unifying model of formal argumentation, where argumentative relations between arguments are represented by assigning acceptance conditions to atomic arguments. Their generality allows them to cover a number of different approaches with varying forms of representing the argumentation structure. Boolean regulatory networks are used to model the dynamics of complex biological processes, taking into account the interactions of biological compounds, such as proteins or genes. These models have proven highly useful for comprehending such biological processes, allowing to reproduce known behaviour and testing new hypotheses and predictions in silico, for example in the context of new medical treatments. While both these approaches stem from entirely different communities, it turns out that there are striking similarities in their appearence. In this paper, we study the relation between these two formalisms revealing their communalities as well as their differences, and introducing a correspondence that allows to establish novel results for the individual formalisms. 1. Introduction between atoms are expressed by arrows (e.g. writing a pa- per influences attendance of a conference in both Vietnam Formal argumentation is one of the major approaches to and Texas), and the acceptance conditions express these knowledge representation and reasoning. In the seminal pa- interactions more precisely. E.g., 𝐢𝑣 = ¬𝑑 ∧ 𝑝 expresses per [1], Dung introduced abstract argumentation frameworks, conference attendance in Vietnam is possible if one has a conceived as directed graphs where nodes represent argu- paper and did not submit it to the conference in Texas. ments and edges between nodes represent attacks. Their meaning is given by so-called argumentation semantics that In systems biology, Biological regulatory networks encode determine which sets of arguments can be reasonably up- interactions between biological specimens or compounds, held together given such an argumentation graph. Various such as proteins or genes, and their interactions, to acquire authors have since remarked that other relations between a better understanding of the complex processes that take arguments are worth consideration, such as, for example, place in cells, as doing so may lead to discoveries and new a dual support relation as in bipolar argumentation frame- theories about living organisms. To abstract from actual con- works [2]. The last decades witnessed a proliferation of centration values, and use thresholds to represent whether extensions of the original formalism that has often made a compound is active or inactive, logical models [5, 6] are it hard to compare the dialects of the different resulting often used instead of quantitative models. Because of that, argumentation formalisms. In an attempt to cope with the they require far less information than quantitative models resulting number of dialects and unify them, abstract di- and are therefore more adequate to deal with incomplete, alectical frameworks (in short, ADFs) were introduced [3]. imprecise, and noisy information regarding the biological Just like abstract argumentation frameworks, ADFs are also system. Among these, Boolean (logical) models or networks directed graphs. However, in ADFs, edges between nodes (BNs), have been extensively used to reproduce known be- do not necessarily represent attacks, but can encode any re- haviour and test new hypotheses in silico, e.g., as models of lationship between arguments. Such generality is achieved gene regulation networks and other biological systems [7]. by associating an acceptance condition with each argument, Example 2. Consider the following toy scenario of a bio- represented as a Boolean formula over the parents of the sphere where four species are potentially present: native argument, expressing the conditions under which the argu- π‘žuagga mussels, invasive 𝑧ebra mussels, π‘Žlgae, and 𝑓 ish. ment can be accepted. ADFs offer a general framework for These species interact as follows: fish feed on mussels, zebra- argumentation-based inference as they are able to capture mussels outcompete quagga, and both kinds of mussels feed all of the major semantics of abstract argumentation [4], on algae. These interactions can be represented using the and even normal logic programs [3]. The following example biological network in Fig. 1.b). Notice that this is a simpli- illustrates a simple ADF. fied representation of a biological network, meant merely to Example 1. You are considering your travel plans for the ease understanding. Influences are represented by arrows, upcoming conference summer. If you manage to write a pa- marked with a β€œ+” if the influence is positive (e.g. since fish per, it will be suitable for a conference in 𝑑exas or in 𝑣ietnam. feed on mussels), and a β€œβˆ’β€ if the influence is negative (e.g. You are only allowed to submit the paper to the conference since zebra mussels outcompete quagga mussels). Further- in Vietnam if you do not submit it to another conference. more, the precise nature of these interactions is encoded by (but the conference in Texas does allow for submission of Boolean functions on the right-hand side of the figure. For papers submitted elsewhere). Both conferences will require example, π‘“π‘ž = ¬𝑧 ∧ π‘Ž expresses that quagga mussels will you to apply for travelling 𝑓 unds. This example can be ex- be alive if there are no zebra-mussels and there are algae. pressed formally in the ADF given in Fig. 1.a). Interactions These examples show striking similarities between these 22nd International Workshop on Nonmonotonic Reasoning, November 2-4, models of two very different subject matters: ADFs and BNs. 2024, Hanoi, Vietnam ⋆ Syntactically, they both use directed graphs to encode inter- This paper has been accepted at LPNMR 2024. actions, and Boolean formulae to express the precise nature $ jesse.heyninck@ou.nl (J. Heyninck); mkn@fct.unl.pt (M. Knorr); jleite@fct.unl.pt (J. Leite) of such interactions. The open question is whether such Β© 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License similarities extend from the syntactic to the semantic level. Attribution 4.0 International (CC BY 4.0). CEUR ceur-ws.org Workshop ISSN 1613-0073 Proceedings a) b) f p Cp = p f a 𝑓z = a Cv = Β¬t β‹€ p + + + + 𝑓q = Β¬z β‹€ a Ct = p _ v t Cf = v ⋁ t z q 𝑓f = z ⋁ q Figure 1: Examples of a) an ADF for Example 1, and b) a BN for Example 2. If that were the case, it would open up a fruitful ground formulas Ξ¦. A set of formulas Ξ¦1 entails another set of for- for the cross-fertilization of both fields, both theoretically, mulas Ξ¦2 , denoted by Ξ¦1 ⊒ Ξ¦2 , if Mod2 (Ξ¦1 ) βŠ† Mod2 (Ξ¦2 ). where established results from one could provide new in- A formula πœ‘ is a tautology if Mod2 (πœ‘) = 𝒱 2 (At) and incon- sights for the other, but also practically, e.g., by allowing sistent if Mod2 (πœ‘) = βˆ…. We compare two possible worlds implementations for one to be used by the other. πœ”1 and πœ”2 by: πœ”1 ≀ πœ”2 iff for every 𝛼 ∈ At, πœ”1 (𝛼) = 1 In this paper, we compare ADFs and BNs. After formally implies πœ”2 (𝛼) = 1. introducing ADFs in Sec. 2, in Sec. 3 we introduce BNs and Commonly though, an ADF 𝐷 = (At, 𝐿, 𝐢) is inter- show that the similarities with ADFs extend from the syn- preted through 3-valued interpretations 𝜈 : At β†’ {1, 0, U} tactic to the semantic level, by pointing in a formally precise adding truth value undecided (U). We denote the set of way what are the equivalent notions, but also what the dif- all 3-valued interpretations over At by 𝒱 3 (At). We define ferences are. Our results show that ADFs are essentially the information order <𝑖 over {1, 0, U} by making U the BNs, creating a fruitful ground for investigating synergies, minimal element: U <𝑖 1 and U <𝑖 0, and † ≀𝑖 ‑ iff as illustrated in Sec. 4. We then conclude in Sec. 5.1 † <𝑖 ‑ or † = ‑ for any †, ‑ ∈ {1, 0, U}. This order is lifted point-wise as follows (given 𝜈, 𝜈 β€² ∈ 𝒱 3 (At)): 𝜈 ≀𝑖 𝜈 β€² iff 𝜈(𝑠) ≀𝑖 𝜈 β€² (𝑠) for every 𝑠 ∈ At. The set of two-valued inter- 2. Abstract Dialectical Frameworks pretations extending a 3-valued interpretation 𝜈 is defined as [𝜈]2 = {πœ” ∈ 𝒱 2 (At) | 𝜈 ≀𝑖 πœ”}. Given a set of 3-valued We recall ADFs following loosely the notation from [3]. interpretations 𝑉 βŠ† 𝒱 3 (At), βŠ“π‘– 𝑉 is the 3-valued interpre- An ADF 𝐷 is a tuple 𝐷 = (At, 𝐿, 𝐢) where At is a fi- tation defined via βŠ“π‘– 𝑉 (𝑠) = † if for every 𝜈 ∈ 𝑉 , 𝜈(𝑠) = †, nite set of atoms, representing arguments or statements, for any † ∈ {1, 0, U}, and βŠ“π‘– 𝑉 (𝑠) = U otherwise. 𝐿 βŠ† At Γ— At is a set of links, representing dependen- All major semantics of ADFs single out three-valued in- cies or attacks from one argument against another, and terpretations in which the truth value of every atom 𝑠 ∈ At 𝐢 = {𝐢𝑠 }π‘ βˆˆAt is a set of total functions (also called accep- is, in some sense, in alignment or agreement with the truth tance functions) 𝐢𝑠 : 2π‘π‘Žπ‘Ÿπ· (𝑠) β†’ {1, 0} for each 𝑠 ∈ At value of the corresponding condition 𝐢𝑠 . The Ξ“-function with π‘π‘Žπ‘Ÿπ· (𝑠) = {𝑠′ ∈ At | (𝑠′ , 𝑠) ∈ 𝐿} and truth values enforces this intuition by mapping an interpretation 𝜈 to a true (1) and false (0). An acceptance function 𝐢𝑠 defines new interpretation Γ𝐷 (𝜈), which assigns to every atom 𝑠 the cases when the statement 𝑠 can be accepted (is true), exactly the truth value assigned by 𝜈 to 𝐢𝑠 , i.e.: depending on the acceptance status of its parents in 𝐷. We often identify an acceptance function 𝐢𝑠 by its equivalent Γ𝐷 (𝜈) : At β†’ {1, 0, U} where 𝑠 β†’ βŠ“π‘– {πœ”(𝐢𝑠 ) | πœ” ∈ [𝜈]2 }. acceptance condition which models the acceptable cases as a propositional formula over At and the usual Boolean con- We also need to define the reduct 𝐷𝜈 of 𝐷 given 𝜈, i.e., nectives ∧ (and), ∨ (or), Β¬ (negation) and β†’ (material impli- 𝐷𝜈 = (At𝜈 , 𝐿𝜈 , 𝐢 𝜈 ) with: (i) At𝜈 = {𝑠 ∈ At | 𝜈(At) = cation). Also, the set of links of 𝐷 is completely determined 1}, (ii) 𝐿𝜈 = 𝐿 ∩ (At𝜈 Γ— At𝜈 ), and (ii) 𝐢 𝜈 = {𝐢𝑠 [{πœ‘ | by 𝐢𝑠 and sometimes left implicit. 𝜈(πœ‘) = 0}/0] | 𝑠 ∈ At𝜈 }, where 𝐢𝑠 [πœ‘/πœ“] is obtained by substituting every occurrence of πœ‘ in 𝐢𝑠 by πœ“. Example 3. In Ex. 1, we find an ADF 𝐷 = Definition 1. Let 𝐷 be an ADF with 𝜈 ∈ 𝒱(At) a 3-valued ({𝑓, 𝑝, 𝑑, 𝑣}, 𝐿, 𝐢) with 𝐿 and 𝐢 as in Fig 1.a). Here, we interpretation. Then, 𝜈 is admissible for 𝐷 iff 𝜈 ≀𝑖 Γ𝐷 (𝜈); omit reflexive arrows (e.g. (𝑝, 𝑝)) to avoid clutter. An ac- 𝜈 is complete for 𝐷 iff 𝜈 = Γ𝐷 (𝜈); 𝜈 is preferred for 𝐷 iff 𝜈 is ceptance condition like 𝐢𝑣 = ¬𝑑 ∧ 𝑝 can be read as β€œπ‘£ is ≀𝑖 -maximal among all admissible models; 𝜈 is grounded for accepted if 𝑑 is not accepted and 𝑝 is accepted. 𝐷 iff 𝜈 is ≀𝑖 -minimal among all complete models; and 𝜈 is Interpretations can be used to formally assign meaning to stable iff 𝜈 is a two-valued model of 𝐷 and {𝑠 ∈ At | 𝜈(𝑠) = these acceptance conditions. An interpretation (also called 1} = {𝑠 ∈ At | 𝑀(𝑠) = 1} where 𝑀 is the grounded model possible world) πœ” is a function πœ” : At β†’ {1, 0}. Let 𝒱 2 (At) of 𝐷𝜈 . We denote by 2V(𝐷), adm(𝐷), cmp(𝐷), prf(𝐷), denote the set of all interpretations for At. We simply write grnd(𝐷), and stb(𝐷) the sets of two-valued, admissible, 𝒱 2 if the set of atoms is implicitly given. An interpretation complete, preferred, grounded, and stable models of 𝐷. πœ” satisfies (or is a model of) an atom π‘Ž ∈ At, denoted by It was been shown that stb(𝐷) βŠ† 2V(𝐷) βŠ† prf(𝐷) βŠ† πœ” |= π‘Ž, if and only if πœ”(π‘Ž) = 1. The satisfaction relation |= cmp(𝐷) βŠ† adm(𝐷) as well as grnd(𝐷) βŠ† cmp(𝐷). is extended to formulas as usual. Then, an interpretation πœ” is a two-valued model of an ADF 𝐷 if, for all 𝑠 ∈ At, πœ” |= 𝑠 Example 4 (Ex. 1 ctd.). The ADF in Ex. 1 has three complete iff πœ” |= 𝐢𝑠 . For sets of formulas Ξ¦, we also define πœ” |= Ξ¦ models 𝜈1 , 𝜈2 , 𝜈3 with: 𝜈1 (𝑝) = 1, 𝜈1 (𝑣) = 0, 𝜈1 (𝑑) = 1 if and only if πœ” |= πœ‘ for every πœ‘ ∈ Ξ¦, and the set of mod- and 𝜈1 (𝑓 ) = 1; 𝜈2 (𝑠) = 0 and 𝜈3 (𝑠) = U for all 𝑠 ∈ At. An els Mod2 (Ξ¦) = {πœ” ∈ 𝒱 2 (At) | πœ” |= Ξ¦} for every set of admissible model that is not complete is 𝜈4 with 𝜈4 (𝑝) = 1, 𝜈4 (𝑣) = 𝜈4 (𝑑) = 𝜈4 (𝑓 ) = U. 𝜈3 is the grounded model, 1 An extended version of this paper with all the proofs is available at whereas 𝜈1 and 𝜈2 are both preferred and two-valued, and https://arxiv.org/abs/2407.02055 only 𝜈2 is stable. _ graph of a BN, links in ADFs commonly do not mention v𝟷 v𝟸 𝑓 v1 = v2 explicitly whether an argument is attacking or supporting. + Still, this can be extracted from the corresponding accep- + + 𝑓v2 = Β¬v1 β‹€ v4 tance conditions, and in some literature [20], the so-called + polarity of links is explicitly represented (see also Section v𝟹 _ v𝟺 𝑓v3 = v1 ⋁ (v2 β‹€ Β¬v4) 3.3). Similarly, the exact representation of regulatory graphs differs in the literature. Using our notation here, we estab- lish this connection between Boolean networks and ADFs Figure 2: Example of a Boolean logical model. formally. Definition 4. Let 𝑀 = (𝑉, 𝐹 ) be a Boolean logical model 3. Boolean Networks of a regulatory network with regulatory graph 𝐺 = (𝑉, 𝐸). We define the corresponding ADF 𝐷𝑀,𝐺 = (𝑉, 𝐿, 𝐹 ) with In this section, we recall Boolean networks as known from 𝐿 = {(𝑒, 𝑣) | (𝑒, 𝑣, 𝑠) ∈ 𝐸}. the literature (see e.g., [8]), first looking at the syntax and Let 𝐷 = (At, 𝐿, 𝐢) be an ADF. We define the corre- then focussing on their semantics. During this presentation, sponding Boolean logical model 𝑀𝐷 of a regulatory net- we will establish sometimes surprising connections to ADFs work as 𝑀𝐷 = (At, 𝐢). The corresponding regulatory as well as notable differences between these two formalisms. graph 𝐺𝐷 = (At, 𝐸) can be obtained from 𝐢 in NNF with 𝐸 = {(𝑒, 𝑣, +) | 𝑒 ∈ 𝐢𝑣 , ¬𝑒 ̸∈ 𝐢𝑣 } βˆͺ {(𝑒, 𝑣, βˆ’) | ¬𝑒 ∈ 𝐢𝑣 , 𝑒 ̸∈ 𝐢𝑣 } βˆͺ {(𝑒, 𝑣, Β±) | 𝑒 ∈ 𝐢𝑣 , ¬𝑒 ∈ 𝐢𝑣 }. 3.1. Syntax The requirement for the acceptance conditions to be in Boolean networks utilize a regulatory graph to represent Negation Normal Form (NNF) is necessary to include the the compounds in the biological process and the principal correct edges in 𝐺𝐷 . Alternatively, one can determine the interactions between them. polarity using Definition 11 below. Either way, as we will Definition 2. A regulatory graph is a directed graph see next, the semantics of Boolean networks is uniquely 𝐺 = (V, 𝐸), where 𝑉 = {𝑣1 , ..., 𝑣𝑛 } is the set of ver- determined by the compounds and their Boolean functions, tices (nodes) representing the regulatory compounds, and i.e., the Boolean logical model, and the regulatory graph can 𝐸 = {(𝑒, 𝑣, 𝑠) : 𝑒, 𝑣 ∈ 𝑉, 𝑠 ∈ {+, βˆ’, Β±}} is the set of be left implicit. signed edges representing the interactions between com- pounds. 3.2. Dynamics An edge with 𝑠 = + is called positive interaction (or acti- BNs allow us to capture the changes over time in a biological vation), representing that 𝑒 activates 𝑣, while an edge with process based on the interactions of the various compounds 𝑠 = βˆ’ is called negative interaction (or inhibition), represent- involved, which should correctly represent the dynamics ing that 𝑒 inhibits 𝑣. Occasionally, 𝑒 may (in combination observable in the real system. We will see that the study of with different compounds) both activate and inhibit another dynamics in BNs correspond to semantics of ADFs. We start compound 𝑣, which is represented with an edge with 𝑠 = Β±. with network states that are used to represent the (current) A node with no incoming edges is called input node, repre- activations of a network’s compounds. senting external stimuli, whose values do not change. Definition 5. The network state of a BN with 𝑛 compounds Example 5. Fig. 2 shows regulatory graph 𝐺 = (V, 𝐸) is a vector 𝑆 = (𝑣1 , ..., 𝑣𝑛 ) where 𝑣𝑖 is the value of the with 𝑉 = {𝑣1 , 𝑣2 , 𝑣3 , 𝑣4 } and 𝐸 = {(𝑣1 , 𝑣2 , βˆ’), variable representing the 𝑖-th compound of the network. (𝑣1 , 𝑣3 , +), (𝑣2 , 𝑣1 , +), (𝑣2 , 𝑣3 , +), (𝑣4 , 𝑣2 , +), (𝑣4 , 𝑣3 , βˆ’)}. Clearly, for Boolean logical models, the number of differ- Boolean logical models then add regulatory functions for ent states in a network is given by 2𝑛 . E.g., if nodes 1 and 3 each compound to specify how different compounds that in Ex. 6 are active and the other two are not, then the state affect the same node interact with each other for that node’s will be represented by 1010. Similar representations are activation. used for interpretations of ADFs (by ordering the atoms), and it is clear that the states in BNs correspond to possible Definition 3. A Boolean logical model 𝑀 of a regula- world of ADFs. tory network is defined as a tuple (V, 𝐹 ) where 𝑉 = The update of the i-th compound 𝑣𝑖 of a network from {𝑣1 , 𝑣2 , ..., 𝑣𝑛 } is the set of variables representing the reg- one discrete time point 𝑑 to the next is then defined as 𝑣𝑖 (𝑑 + ulatory compounds of the network such that 𝑣𝑖 can be as- 1) = 𝑓𝑖 (𝑆(𝑑)) for state 𝑆(𝑑) at time 𝑑, which clearly exactly signed to a value in {0, 1}, and 𝐹 = {𝑓1 , 𝑓2 , ..., 𝑓𝑛 } is the corresponds to the evaluation of an acceptance condition set of Boolean functions such that 𝑓𝑖 defines the value of 𝑣𝑖 in ADFs. We can then use state transition graphs [9] to and where 𝑓𝑖 = 𝑣𝑖 if 𝑣𝑖 is an input node. describe how networks, and thus the modelled biological Regulatory functions of input nodes may sometimes be systems, evolve over time. omitted (cf. Fig. 2), which means that 𝑓𝑖 = 𝑣𝑖 , but commonly, Definition 6. A State Transition Graph (STG) is a directed we use the explicit representation. graph 𝐺𝑆𝑇 𝐺 = (𝑆, 𝑇 ) where 𝑆 is the set of vertices repre- Example 6. Fig. 2 presents a Boolean logical model with senting the different states of the network, and 𝑇 is the set 𝐺 from Ex. 5 and regulatory functions for 𝐺 on the right. of edges representing the viable transitions between states according to given update scheme. We can observe that, syntactically, a Boolean network is strikingly similar to an abstract dialectical framework. The Two update schemes are employed to update the values only difference is that, unlike the edges in the regulatory of nodes in a BN: the synchronous and the asynchronous a) 0110 1110 0111 1111 b) 0110 1110 0111 1111 0100 1100 0101 1101 0100 1100 0101 1101 0010 1010 0011 1011 0010 1010 0011 1011 0000 1000 0001 1001 0000 1000 0001 1001 Figure 3: STG of the model in Ex. 6 for a) synchronous updates and b) asynchronous updates, both with 𝑣4 inactive on the left, and active on the right (adapted from [12]). updating scheme [10, 11]. Note that, given a Boolean logi- models of the corresponding ADF. cal model, the state transition graphs for the synchronous Proposition 1. Let 𝐺𝑆𝑇 𝐺 be the synchronous state transi- updating scheme and asynchronous updating scheme are tion graph of the Boolean Model 𝑀 with regulatory graph uniquely determined. 𝐺, and 𝐷𝑀,𝐺 the corresponding ADF. Then, πœ” is a stable In the synchronous updating scheme, at each time step, state of 𝐺𝑆𝑇 𝐺 iff πœ” is a two-valued model of 𝐷𝑀,𝐺 . all compounds are updated simultaneously, i.e., given a state 𝑆 = (𝑣1 , ..., 𝑣𝑛 ), the new state is obtained as 𝑆 β€² = To the best of our knowledge, the more general notion of (𝑓1 (𝑆), ..., 𝑓𝑛 (𝑆)). Each network state has at most one a trap set has not been investigated in the context of ADFs. successor (cf. Fig. 3.a), which is sometimes argued to be This is not surprising, as it has a clear meaning and use in biologically less realistic and less accurate for analysis. Yet, biological networks, but not so much in argumentation: synchronous updates are still regularly used [13], and many Example 7. Consider the ADF 𝐷 = ({π‘Ž, 𝑏, 𝑐}, 𝐿, 𝐢) with of the concepts below, such as trap spaces, are independent πΆπ‘Ž = ¬𝑐, 𝐢𝑏 = Β¬π‘Ž and 𝐢𝑐 = ¬𝑏. Then {000, 111} is a of the used scheme. trap set and an attractor, but their argumentative interpre- In the asynchronous updating scheme, at each time step, tation is not clear: if we interpret π‘Ž, 𝑏, and 𝑐 as arguments one or more regulatory functions may be applied [13]. This that attack each other, the stability under transitions of is closer to what is observable in real systems, since these {000, 111}, interesting in a biological interpretation, is of changes seldomly tend to take place simultaneously. With n less interest in argumentation. compounds in a network, and the frequently used, particular case of exactly one function being applied at each time step, More surprisingly, we will now see that many other se- each state can have at most 𝑛 possible state transitions mantics for ADFs have a natural counterpart in Boolean (including a transition to itself - cf. Fig. 3.b). networks. For example, there has been a lot of interest There are certain cycles of states in which these networks in so-called subspaces of regulatory graphs [8], which are reside most of the time. These cycles are a trap of sorts, since sets of interpretations for which assignments of some vari- as soon as a network enters a cycle’s state, it is unable to exit ables are fixed. These are represented as assignments the cycle. These traps, called attractors, are linked to many π‘š : 𝑉 ↦→ {0, 1, ⋆} of the variables 𝑉 to the β€œclassical” important cellular processes, such as phenotypes, cell cycle values 0 and 1 or the value ⋆, intuitively representing that phases, cell growth, differentiation, apoptosis, and more the respective variable has no fixed assignment. This means [14]. Because the number of states in a network is finite, that for every 𝑣 ∈ 𝑉 for which π‘š(𝑣) = ⋆, the subspace transitions from all states eventually lead to an attractor. contains both states that assign 0 to 𝑣 and states that assign All states that lead to a certain attractor form its attraction 1 to 𝑣. Trap spaces have received a lot of attention in the basin. literature on Boolean networks as finding them is computa- Attractors have other relevant characteristics. One such tionally easier then finding any trap set [16], while they are characteristic is that, from any state belonging to an attrac- still guaranteed to contain a trap set [8]. tor, it is possible to find a path of attractor states to any other Definition 8. A subspace π‘š of a regulatory graph (𝑉, 𝐸) state in that attractor. Another important property is that is a mapping π‘š : 𝑉 ↦→ {0, 1, ⋆}. We call 𝑣 ∈ 𝑉 fixed if there are no state transitions from attractor states to states π‘š(𝑣) ∈ {0, 1} and free if π‘š(𝑣) = ⋆, and π·π‘š is the set of outside of the attractor. Attractors can also be classified all fixed variables in π‘š. We let 𝑆[π‘š] := {𝑠 ∈ 𝑆 | βˆ€π‘£ ∈ under different types. The left image of Fig. 3.a) shows an π·π‘š : 𝑠(𝑣) = π‘š(𝑣)}. example of a stable state (or point attractor) in the white- colored 0000 state. Stable states are attractors that contain We sometimes abuse notation and identify a subspace π‘š only a single state. When that is not the case, the attractor with its expanded variant 𝑆[π‘š]. is denoted as a cyclic (or complex) attractor, visualized in the An interesting observation is that subspaces, interpreted right image of Fig. 3.a). There, we have a complex attractor as their representative set of Boolean valuations 𝑆[π‘š], cor- comprised of four states: 0101, 1101, 1011 and 0011 [15]. respond exactly to the completions of the subspaces, inter- preted as three-valued interpretations: Definition 7. Given an STG 𝐺𝑆𝑇 𝐺 = (𝑆, 𝑇 ), a set 𝑆 β€² βŠ† 𝑆 Proposition 2. Let π‘š be a subspace π‘š, and πœˆπ‘š : 𝑉 ↦→ is a trap set of 𝐺𝑆𝑇 𝐺 if, for every πœ” ∈ 𝑆 β€² , (πœ”, πœ” β€² ) ∈ 𝑇 {0, 1, U} defined by implies πœ” β€² ∈ 𝑆 β€² . An attractor is a βŠ†-minimal trap set. A {οΈƒ stable state of 𝐺 is a singleton trap set of 𝐺. π‘š(𝑣) if 𝑣 ∈ π·π‘š πœˆπ‘š (𝑣) = (1) We obtain that stable states of a transition graph 𝐺 under U otherwise. synchronous update scheme coincide with the two-valued It holds that [πœˆπ‘š ]2 = 𝑆[π‘š]. Subspaces that are also trap sets are of special interest in 3.3. Subclasses of Boolean Networks the literature on Boolean networks. An interesting observation is that both the literature on Definition 9. A trap space is a subspace π‘š for which 𝑆[π‘š] ADFs and the literature on Boolean Networks has identified is a trap set. certain subclasses of frameworks for which the computa- tional complexity of computational tasks decreases. In fact, Trap spaces, interpreted as three-valued interpretations both strands of literature have identified the same subclass! (see Proposition 2) correspond to admissible interpretations: In the literature on ADFs, these frameworks are called bipo- lar ADFs, whereas in the literature on Boolean networks, Proposition 3. Let 𝑀 be a Boolean Model with regulatory they are called sign-definite. graph 𝐺, and 𝐷𝑀,𝐺 the corresponding ADF: π‘š is a trap space of M iff πœˆπ‘š is admissible in 𝐷𝑀,𝐺 . Definition 10. A Boolean function 𝑓 : {0, 1}𝑛 ↦→ {0, 1} is increasing monotone [decreasing monotone] On the other hand, the complete semantics does not seem on 𝑖 if 𝑓 (𝑣1 , . . . , 𝑣𝑖 , . . . , 𝑣𝑛 ) ≀ 𝑓 (𝑣1 , . . . , 𝑣𝑖′ , . . . , 𝑣𝑛 ) to have a direct counterpart in Boolean networks. [𝑓 (𝑣1 , . . . , 𝑣𝑖 , . . . , 𝑣𝑛 ) β‰₯ 𝑓 (𝑣1 , . . . , 𝑣𝑖′ , . . . , 𝑣𝑛 )], where Example 8. Consider the ADF 𝐷 = ({π‘Ž, 𝑏}, 𝐿, 𝐢) with 𝑣𝑖 = 0 and 𝑣𝑖′ = 1. It is sign-definite if it is increasing πΆπ‘Ž = {π‘Ž ∨ Β¬π‘Ž} and 𝐢𝑏 = 𝑏. Let us take a look at the STG or decreasing monotone for every 𝑖 = 1 . . . 𝑛. A Boolean for synchronous updates first: logical model (𝑉, 𝐹 ) is sign-definite if every Boolean func- tion in 𝐹 is sign-definite. 00 10 11 01 It is well-known that a Boolean function is sign-definite if and only if it can be represented by a formula in disjunctive There are three trap spaces: ⋆⋆, ⋆1, and 11. By Prop. 3, this normal form in which all occurrences of a given literal are corresponds to the interpretations UU and 11. However, either negated or non-negated [18]. the unique complete interpretation is 11. We now recall bipolar ADFs [19]. We might conjecture that the complete interpretations Definition 11. Given a Boolean function 𝑓 : {0, 1}𝑛 ↦→ correspond to the minimal trap spaces, but that is not the {0, 1}: case either. β€’ 𝑖 ≀ 𝑛 is supporting iff 𝑓 (𝑣1 , . . . , 𝑣𝑖 , . . . , 𝑣𝑛 ) = 1 Example 9. Consider the ADF 𝐷 = ({π‘Ž}, 𝐿, 𝐢) with implies 𝑓 (𝑣1 , . . . , 𝑣𝑖′ , . . . , 𝑣𝑛 ) = 1 where 𝑣𝑖 = 0 πΆπ‘Ž = {π‘Ž}. There are three trap spaces: ⋆, 1, and 0. The and 𝑣𝑖′ = 1, corresponding interpretations U, 1 and 0 are not only ad- β€’ 𝑖 ≀ 𝑛 is attacking iff 𝑓 (𝑣1 , . . . , 𝑣𝑖 , . . . , 𝑣𝑛 ) = 0 missible but also complete. However, U is not a minimal implies 𝑓 (𝑣1 , . . . , 𝑣𝑖′ , . . . , 𝑣𝑛 ) = 0 where 𝑣𝑖 = 0 trap space. and 𝑣𝑖′ = 1. We further note that there has been some interest in An ADF is bipolar iff for every π‘Ž ∈ At, every 𝑏 ∈ par𝐷 (π‘Ž) maximal and minimal trap spaces [15] in the literature on is supporting, attacking or both in πΆπ‘Ž . BNs. In more detail, trap sets are compared as follows: π‘š1 ≀ π‘š2 iff 𝑆[π‘š1 ] βŠ† 𝑆[π‘š2 ]. It can be easily observed It was shown that an ADF is bipolar iff every acceptance that this is the reverse of the information order ≀𝑖 known formula is equivalent to a formula that is syntactically bipo- from ADFs: lar, i.e., no atoms occurs both positively and negatively [20]. From this, we can show that these two special cases coincide: Proposition 4. Let π‘š1 , π‘š2 be two subspaces. Then π‘š1 ≀ π‘š2 iff πœˆπ‘š2 ≀𝑖 πœˆπ‘š1 . Corollary 1. A Boolean model is sign-definite iff the cor- responding ADF is bipolar. Minimal trap spaces are trap spaces π‘š1 such that there is no trap space π‘š2 < π‘š1 . Maximal trap spaces are trap spaces π‘š1 s.t. there is no trap space π‘š2 > π‘š1 and 𝑆[π‘š1 ] ΜΈ= 4. Insights from Boolean Networks 𝑆, i.e., the trivial trap space is excluded by definition. Based on the established correspondence, we provide exam- Proposition 5. Let 𝑀 be a BN with regulatory graph 𝐺, ples of insights from the literature on Boolean Networks and 𝐷𝑀,𝐺 the corresponding ADF: π‘š is a minimal trap that are directly relevant for ADFs. space of M iff πœˆπ‘š is preferred in 𝐷𝑀,𝐺 . However, maximal trap spaces do not correspond to the 4.1. Complexity of Counting Problems grounded model. The reason is that in BNs, the trivial trap For many applications in KR, being able to know the number space is excluded. E.g., in Ex. 3, 𝜈3 is the grounded model, of solutions is important. For many formalisms, including but does not correspond to a maximal trap space as it is abstract argumentation [21], according decision problems trivial trap space. Finally, we note that the concept of stable have been studied in depth. For ADFs, such a study is miss- model from ADFs has no clear counterpart in BNs. Indeed, ing. Due to existing results from the literature on BNs we the main motivation behind stable models is to exclude can start filling this gap. self-supporting arguments (see e.g., Ex. 4 where 𝜈1 with 𝑝 For example, Bridoux et al. [22] study the complexity supporting itself via 𝐢𝑝 = 𝑝 is excluded). In BNs, there of deciding whether the number of stable states in a BN is is nothing a priori wrong with such self-supporting stable above (or below) a given bound π‘˜. Given the correspondence states, and it might often even have a clear biological mean- between BNs and ADFs established here, we immediately ing, e.g., since algae are self-reproducing. obtain the following corresponding results: Corollary 2. Deciding whether the maximal number of The final result we discuss is an upper bound on the two-valued models in an ADF 𝐷 is larger or equal than number of stable states in terms of the number of feedback π‘˜ is: in P for fixed π‘˜ = 1; NP-complete for fixed π‘˜ β‰₯ 2; vertex sets (FVSs). An FVS of a digraph 𝐺 = (𝑉, 𝐸) is NEXPTIME-complete for arbitrary π‘˜; and NP#P -complete defined to be a set of vertices that contains at least one for an arbitrary π‘˜ if the maximum in-degree of 𝐷 is bounded vertex of each cycle of 𝐺. The minimum number of vertices by a constant 𝑑 β‰₯ 2. of a FVS is denoted by 𝜏 (𝐺). Deciding whether the minimal number of two-valued models in an ADF 𝐷 is smaller than π‘˜ is: NEXPTIME- Proposition 8 ([26]). A Boolean logical model 𝑁 = (𝑉, 𝐹 ), complete for arbitrary π‘˜ without any bound on the in- where |𝑉 βˆ’ (𝑣)| β‰₯ 1 for all 𝑣 ∈ 𝑉 , has at most 2𝜏 (𝑁 ) stable degree; NPNP -complete for fixed π‘˜ β‰₯ 2, if the maximum states. in-degree of 𝐷 is bounded by a constant 𝑑 β‰₯ 2; NP#P - This carries over to ADFs as follows. complete for an arbitrary π‘˜ if the maximum in-degree of 𝐷 is bounded by a constant 𝑑 β‰₯ 2.2 Corollary 5. An ADF 𝐷 = (At, 𝐿, 𝐢) s.t. every argument has at least one attacker has at most 2𝜏 ((At,𝐿)) stable states. 4.2. Existence of Fixpoints There is a large line of work in the literature on Boolean net- 5. Conclusion works that studies structural properties of Boolean networks that affect the existence (and the number) of fixed points. We have reviewed the main syntactic similarities between Such work immediately translates to the existence of two- ADFs and BNs, and demonstrated that these extend in large valued models in ADFs. E.g., several works [23, 24, 25, 26] parts to the semantical level. Furthermore, we have shown provide a theoretical analysis of the existence of fixpoints the fruitfulness of this connection by deriving results on in sign-definite BN in relation to structural parameters of complexity and existence of semantics for ADFs based on the corresponding Boolean networks. We follow Aracena existing results for BNs. We hope that our results will lead [26] in defining a path in a BN as positive if the number of to further cross-contamination between these two fields, negative arcs is even, and negative otherwise. such as the use of implementations or benchmarks. The first few results study the connection between cycles, their parity, and the existence and number of fixpoints: Acknowledgments We thank the anonymous reviewers for their valuable feedback. This work is partially supported Proposition 6. If a sign-definite BN has: no cycles, then it by project BIO-REVISE (2023.13327.PEX) and NOVA LINCS has a unique stable state [23]; no positive cycles, then it has ref. UIDB/04516/2020 (https://doi.org/10.54499/UIDB/04516/ at most one stable state [24]; no negative cycles, then it has 2020) and ref. UIDP/04516/2020 (https://doi.org/10.54499/ at least one stable state [25]. If a BN 𝑁 has a strongly con- UIDP/04516/2020) with the financial support of FCT. nected component 𝐻 such that all cycles of 𝐻 are negative and for each arc (𝑣𝑖 , 𝑣𝑗 ) in the 𝑁 , 𝑣𝑗 ∈ 𝐻 then 𝑣𝑖 ∈ 𝐻, then 𝑁 has no stable states [26]. References We derive the following corollary for ADFs: [1] P. M. Dung, On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic Corollary 3. Let a bipolar ADF 𝐷 be given. Then: if 𝐷 has programming and n-person games, AI 77 (1995) 321– no cycles, then it has a unique two-valued model; if 𝐷 has 358. no positive cycles, then it has at most one two-valued model; [2] C. Cayrol, M.-C. Lagasquie-Schiex, On the accept- if 𝐷 has no negative cycles, then it has at least one two- ability of arguments in bipolar argumentation frame- valued model. If 𝐷 has a strongly connected component works, in: European Conference on Symbolic and 𝐻 such that all cycles of 𝐻 are negative and for each arc Quantitative Approaches to Reasoning and Uncer- (𝑣𝑖 , 𝑣𝑗 ) in the 𝑁 , 𝑣𝑗 ∈ 𝐻 then 𝑣𝑖 ∈ 𝐻, then 𝑁 has no tainty, Springer, 2005, pp. 378–389. two-valued models. [3] G. Brewka, H. Strass, S. Ellmauthaler, J. P. Wallner, One finds also more intricate results on the existence of S. Woltran, Abstract dialectical frameworks revisited, fixpoints in the literature, for example in terms of so-called in: Procs. of ICJAI, 2013. non-expansive maps, that guarantee the existence of stable [4] S. Polberg, Understanding the abstract dialectical states [27]. These fall outside the scope of this paper. framework, in: Procs. of JELIA, volume 10021 of LNCS, Some work has also investigated the connection between Springer, 2016, pp. 430–446. the existence of stable states and the structure of the corre- [5] L. Glass, S. A. Kauffman, The logical analysis of contin- sponding BN: uous, non-linear biochemical control networks, Jour- nal of Theoretical Biology 39 (1973) 103–129. Proposition 7 ([26]). If a BN has at least one stable state, [6] R. Thomas, Boolean formalization of genetic control then it has at least one positive cycle. circuits, Journal of Theoretical Biology 42 (1973) 563– 585. We derive the following corollary for ADFs: [7] L. Salinas, L. GΓ³mez, J. Aracena, Existence and non Corollary 4. An ADF has a two-valued model has at least existence of limit cycles in boolean networks, in: Au- one positive cycle. tomata and Complexity, volume 42, Springer, 2022, pp. 233–252. [8] H. Klarner, A. Bockmayr, H. Siebert, Computing max- imal and minimal trap spaces of boolean networks, 2 The maximum in-degree of an ADF (At, 𝐿, 𝐢) is the maximal number Nat. Comput. 14 (2015) 535–544. of different literals occurring in an acceptance formula πΆπ‘Ž ∈ 𝐢 . [9] A. Naldi, E. Remy, D. Thieffry, C. Chaouiya, Dynami- cally consistent reduction of logical regulatory graphs, Theor. Comput. Sci. 412 (2011) 2207–2218. [10] A. Faure, A. Naldi, C. Chaouiya, D. Thieffry, Dynami- cal analysis of a generic boolean model for the control of the mammalian cell cycle, ISMB (Supplement of Bioinformatics) 22 (2006) 124–131. [11] A. Garg, A. D. Cara, I. Xenarios, L. Mendoza, G. D. Micheli, Synchronous versus asynchronous modeling of gene regulatory networks, Bioinformatics 24 (2008) 1917–1925. [12] F. Gouveia, Model Revision of Boolean Logical Mod- els of Biological Regulatory Networks, Ph.D. thesis, Instituto Superior TΓ©cnico, Universidade de Lisboa, 2021. [13] J. D. Schwab, S. D. KΓΌhlwein, N. Ikonomi, M. KΓΌhl, H. A. Kestler, Concepts in boolean network modeling: What do they all mean, Computational and Structural Biotechnology 18 (2020) 571–582. [14] M. Hopfensitz, C. MΓΌssel, M. Maucher, H. A. Kestler, Attractors in boolean networks: a tutorial, Comput. Stat. 28 (2012) 19–36. [15] H. Klarner, A. Bockmayr, H. Siebert, Computing sym- bolic steady states of boolean networks, in: Procs. of ACRI, volume 8751 of LNCS, Springer, 2014, pp. 561– 570. [16] K. Moon, K. Lee, L. PaulevΓ©, Computational complex- ity of minimal trap spaces in boolean networks, arXiv preprint arXiv:2212.12756 (2022). [17] J. Heyninck, G. Kern-Isberner, An epistemic inter- pretation of abstract dialectical argumentation, in: Computational Models of Argument, 2020, pp. 227– 238. [18] M. Anthony, Discrete mathematics of neural networks: selected topics, SIAM, 2001. [19] H. Strass, Approximating operators and semantics for abstract dialectical frameworks, Artif. Intell. 205 (2013) 39–70. [20] H. Strass, Expressiveness of two-valued semantics for abstract dialectical frameworks, Journal of Artificial Intelligence Research 54 (2015) 193–231. [21] J. K. Fichte, M. Hecher, A. Meier, Counting complexity for reasoning in abstract argumentation, in: Procs. of AAAI, 2019, pp. 2827–2834. [22] F. Bridoux, A. Durbec, K. Perrot, A. Richard, Com- plexity of fixed point counting problems in boolean networks, J. Comput. Syst. Sci. 126 (2022) 138–164. [23] F. Robert, Iterations sur des ensembles finis et auto- mates cellulaires contractants, Linear Algebra and its applications 29 (1980) 393–412. [24] Γ‰. Remy, P. Ruet, D. Thieffry, Graphic requirements for multistability and attractive cycles in a boolean dynamical framework, Advances in Applied Mathe- matics 41 (2008) 335–350. [25] A. Richard, Negative circuits and sustained oscillations in asynchronous automata networks, Advances in Applied Mathematics 44 (2010) 378–392. [26] J. Aracena, Maximum number of fixed points in reg- ulatory boolean networks, Bull. Math. Biol. 70 (2008) 1398–1409. [27] A. Richard, Local negative circuits and fixed points in non-expansive boolean networks, Discrete Applied Mathematics 159 (2011) 1085–1093. A. Proofs for Section 3 (Boolean Proposition 5. Let 𝑀 be a BN with regulatory graph 𝐺, and 𝐷𝑀,𝐺 the corresponding ADF: π‘š is a minimal trap Networks) space of M iff πœˆπ‘š is preferred in 𝐷𝑀,𝐺 . Proposition 1. Let 𝐺𝑆𝑇 𝐺 be the synchronous state transi- Proof. With Proposition 3, π‘š is a trap space of M iff πœˆπ‘š is tion graph of the Boolean Model 𝑀 with regulatory graph admissible in 𝐷𝑀,𝐺 . Suppose now towards a contradiction 𝐺, and 𝐷𝑀,𝐺 the corresponding ADF. Then, πœ” is a stable that π‘š is a minimal trap space, yet πœˆπ‘š is not preferred, state of 𝐺𝑆𝑇 𝐺 iff πœ” is a two-valued model of 𝐷𝑀,𝐺 . i.e. there is some admissible 𝜈 with πœˆπ‘š <𝑖 𝜈. Then with Proof. This follows from the following list of equivalences: Proposition 4 and Proposition 3, there is a trap space π‘šπœˆ < πœ” is a stable state for the synchronous transition π‘š, contradicting π‘š being a minimal trap space. graph of 𝑀 = (𝑉, 𝐹 ) The reader might be somewhat surprised by the fact that ⇔ 𝑠𝑖 = 𝑓𝑖 (πœ”) for every 𝑠𝑖 ∈ At links can be both attacking and supporting. However, the ⇔ πœ”(𝑠) = πœ”(𝐢𝑠 ) for every 𝑠 ∈ At only possibility for that being the case, is if the link is re- ⇔ πœ” is a two-valued model of 𝐷. dundant: Proposition 10. Consider an ADF 𝐷 = (At, 𝐿, 𝐢) with Proposition 2. Let π‘š be a subspace π‘š, and πœˆπ‘š : 𝑉 ↦→ 𝑠1 , 𝑠2 ∈ At and 𝑠2 being supporting and attacking in {0, 1, U} defined by 𝐢𝑠1 . For every 𝑣1 , 𝑣2 ∈ 𝒱 2 (At) s.t. 𝑣1 (𝑠2 ) ΜΈ= 𝑣2 (𝑠2 ) {οΈƒ and 𝑣1 (𝑠) = 𝑣2 (𝑠) for every 𝑠 ∈ At, Γ𝐷 (𝑣1 )(𝑠1 ) = π‘š(𝑣) if 𝑣 ∈ π·π‘š πœˆπ‘š (𝑣) = (1) Γ𝐷 (𝑣1 )(𝑠1 ). U otherwise. Corollary 1. A Boolean model is sign-definite iff the cor- It holds that [πœˆπ‘š ]2 = 𝑆[π‘š]. responding ADF is bipolar. Proof. It suffices to observe that πœˆπ‘š ≀𝑖 πœ” iff πœ”(𝑣) = π‘š(𝑣) Proof. We first recall that, given a formula πœ‘, the polarity of for every 𝑣 ∈ π·π‘š . an atom π‘Ž in πœ‘ is determined by the number of negations on the path from the root of the formula tree to the atom, and Proposition 3. Let 𝑀 be a Boolean Model with regulatory is positive if this number is even, and negative otherwise. graph 𝐺, and 𝐷𝑀,𝐺 the corresponding ADF: π‘š is a trap For example, in Β¬(π‘Ž ∧ ¬𝑏), π‘Ž occurs negatively and 𝑏 occurs space of M iff πœˆπ‘š is admissible in 𝐷𝑀,𝐺 . positively. A propositional formula is syntactically bipolar if no atom π‘Ž occurs both positively and negatively in πœ‘. Proof. We first need some preliminaries due to Klarner et Clearly, an acceptance condition is supporting respec- al. [8]. Given a boolean function 𝑓 , 𝑓 [π‘š] is the expression tively attacking iff it is increasing respectively decreasing obtained by stituting every occurence of some 𝑣 ∈ π·π‘š monotone. The rest of the proof is an immediate conse- in 𝑓 by π‘š(𝑣). For example, given π‘š = 0 ⋆ 1 and 𝑓 = quence of [20, Theorem 1], which implies that an ADF (π‘Ž ∨ 𝑏) ∧ 𝑐, 𝑓 [π‘š] = (0 ∨ 1) ∧ 𝑐. We let π‘ˆπ‘š := {𝑣𝑖 ∈ 𝑉 | 𝐷 = (At, 𝐿, 𝐢) is bipolar iff, for every 𝑠 ∈ At, 𝐢𝑠 is syn- 𝑓𝑖 [π‘š] is constant} and define 𝐹 [π‘š] : 𝑉 ↦→ {0, 1, U} as: tactically bipolar. {οΈƒ 𝑓𝑖 [π‘š] if 𝑣𝑖 ∈ π‘ˆπ‘š 𝐹 [π‘š](𝑣𝑖 ) = (2) ⋆ otherwise The core of the proof depends on the following result: Proposition 9 ([8], Theorem 1). A space π‘š is a trap set if and only if 𝑆[π‘š] βŠ† 𝑆[𝐹 [π‘š]]. Indeed, with Proposition 2, [πœˆπ‘š ]2 βŠ† [𝜈𝐹 [π‘š] ]2 , i.e. πœˆπ‘š ≀𝑖 𝜈𝐹 [π‘š] . We now show that Γ𝐷𝑀,𝐺 [πœˆπ‘š ] = 𝜈𝐹 [π‘š] . Recall that Γ𝐷𝑀,𝐺 [πœˆπ‘š ](𝑣𝑖 ) = βŠ“π‘– {πœ”(𝐢𝑠 ) | πœ” ∈ [πœˆπ‘š ]2 }. We can safely assume that 𝐢𝑠 is in conjunctive normal form, as Γ𝐷𝑀,𝐺⋀︀ is⋁︀ invariant under classical β‹€οΈ€ equivalences. Let 𝐢𝑠 = 𝑛 βˆ†π‘– . Then 𝑓𝑠 [π‘š] = 𝑛 𝜎(βˆ†π‘– ) where ⋁︀ 𝑖=1 𝑖=1 𝜎(βˆ†) is obtained by replacing every occurrence of some 𝑣 ∈ π·π‘š by π‘š(𝑣). Suppose now 𝐹 [π‘š](𝑠) = 0. This means there ⋁︀ is some 𝑖 = 1, . . . , 𝑛 s.t. 𝜎(βˆ†π‘– ) = {0}. Thus, βŠ“π‘– {πœ”(β‹€οΈ€ βˆ†β‹οΈ€ 𝑖 ) | πœ” ∈ [πœˆπ‘š ] } = 0 which implies 2 that βŠ“π‘– {πœ”( 𝑛 𝑖=1 βˆ† 𝑖 ) | πœ” ∈ [𝜈 π‘š ] } = 0. The cases 2 for 𝐹 [π‘š](𝑠) = 1 and 𝐹 [π‘š](𝑠) = ⋆ are similar. Proposition 4. Let π‘š1 , π‘š2 be two subspaces. Then π‘š1 ≀ π‘š2 iff πœˆπ‘š2 ≀𝑖 πœˆπ‘š1 . Proof. With Proposition 2 from [17], πœˆπ‘š2 ≀𝑖 πœˆπ‘š1 iff for every 𝑠 ∈ At iff [πœˆπ‘š2 ]2 βŠ‡ [πœˆπ‘š1 ]2 . As 𝑆[π‘šπ‘– ] = [πœˆπ‘šπ‘– ]2 for 𝑖 = 1, 2 (Proposition 2), we obtain that πœˆπ‘š2 ≀𝑖 πœˆπ‘š1 iff 𝑆[π‘š1 ] βŠ† 𝑆[π‘š2 ]. By definition of ≀, πœˆπ‘š2 ≀𝑖 πœˆπ‘š1 iff π‘š1 ≀ π‘š2 .