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 diferent 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 diferent 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 diferences, and introducing a correspondence that allows to establish novel results for the individual formalisms.
Formal argumentation is one of the major approaches to
knowledge representation and reasoning. In the seminal
paper [
Example 1. You are considering your travel plans for the upcoming conference summer. If you manage to write a paper, it will be suitable for a conference in exas or in ietnam. You are only allowed to submit the paper to the conference in Vietnam if you do not submit it to another conference. (but the conference in Texas does allow for submission of papers submitted elsewhere). Both conferences will require you to apply for travelling unds. This example can be expressed formally in the ADF given in Fig. 1.a). Interactions 22nd International Workshop on Nonmonotonic Reasoning, November 2-4, 2024, Hanoi, Vietnam ⋆ This paper has been accepted at LPNMR 2024. $ jesse.heyninck@ou.nl (J. Heyninck); mkn@fct.unl.pt (M. Knorr); jleite@fct.unl.pt (J. Leite) © 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). between atoms are expressed by arrows (e.g. writing a paper influences attendance of a conference in both Vietnam and Texas), and the acceptance conditions express these interactions more precisely. E.g., = ¬ ∧ expresses conference attendance in Vietnam is possible if one has a paper and did not submit it to the conference in Texas.
In systems biology, Biological regulatory networks encode
interactions between biological specimens or compounds,
such as proteins or genes, and their interactions, to acquire
a better understanding of the complex processes that take
place in cells, as doing so may lead to discoveries and new
theories about living organisms. To abstract from actual
concentration values, and use thresholds to represent whether
a compound is active or inactive, logical models [
These examples show striking similarities between these models of two very diferent subject matters: ADFs and BNs. Syntactically, they both use directed graphs to encode interactions, and Boolean formulae to express the precise nature of such interactions. The open question is whether such similarities extend from the syntactic to the semantic level. v t Cv = ¬t ⋀ p Ct = p Cf = v ⋁ t b) + f z +
+ _ a q + z = a q = ¬z ⋀ a f = z ⋁ q
We recall ADFs following loosely the notation from [
At ×
At is a set of links, representing dependentance functions) : 2() cies or attacks from one argument against another, and = {}∈At is a set of total functions (also called accep→ {1, 0} for each ∈ At with () = {′ ∈ At | (′, ) ∈ } and truth values true (1) and false (0). An acceptance function defines the cases when the statement can be accepted (is true), depending on the acceptance status of its parents in . We often identify an acceptance function by its equivalent acceptance condition which models the acceptable cases as a propositional formula over At and the usual Boolean connectives ∧ (and), ∨ (or), ¬ (negation) and → (material implication). Also, the set of links of is completely determined by and sometimes left implicit.
ADF = ({, , , }, , ) with and as in Fig 1.a). Here, we omit reflexive arrows (e.g. (, )) to avoid clutter. An acaccepted if is not accepted and is accepted. ceptance condition like = ¬ ∧ can be read as “ is els Mod2(Φ) =
Interpretations can be used to formally assign meaning to these acceptance conditions. An interpretation (also called possible world) is a function : At → {1, 0}. Let 2(At) denote the set of all interpretations for At. We simply write 2 if the set of atoms is implicitly given. An interpretation satisfies
(or is a model of) an atom ∈ At, denoted by |= , if and only if () = 1. The satisfaction relation |= is extended to formulas as usual. Then, an interpretation is a two-valued model of an ADF if, for all ∈ At, |= if |= . For sets of formulas Φ , we also define |= Φ if and only if |= for every ∈ Φ , and the set of mod{ ∈ 2(At) | |= Φ } for every set of 1An extended version of this paper with all the proofs is available at formulas Φ . A set of formulas Φ 1 entails another set of formulas Φ 2, denoted by Φ 1 ⊢ Φ 2, if Mod2(Φ 1) ⊆ A formula is a tautology if Mod2() = 2(At) and inconMod2(Φ 2). sistent if Mod2() = ∅ 1 and 2 by: 1 ≤ implies 2( ) = 1.
. We compare two possible worlds 2 if for every ∈ At, 1( ) = 1
Commonly though, an ADF = (At, , ) is interpreted through 3-valued interpretations : At → {1, 0, U} adding truth value undecided (U). We denote the set of all 3-valued interpretations over At by 3(At). We define the information order < over {1, 0, U} by making U the minimal element: U
< 1 and U < 0, and † ≤ ‡ if † < ‡ or † = ‡ for any †, ‡ ∈ {1, 0, U}. This order is lifted point-wise as follows (given , ′ ∈ 3(At)): ≤ ′ if () ≤ ′() for every ∈ At. The set of two-valued interpretations extending a 3-valued interpretation is defined as [ ]2 = { ∈ 2(At) | ≤ }. Given a set of 3-valued interpretations ⊆ tation defined via
⊓ () = † if for every ∈ , () = †, for any † ∈ {1, 0, U}, and ⊓ () = U otherwise.
All major semantics of ADFs single out three-valued interpretations in which the truth value of every atom ∈ At is, in some sense, in alignment or agreement with the truth value of the corresponding condition . The Γ -function enforces this intuition by mapping an interpretation to a new interpretation Γ ( ), which assigns to every atom exactly the truth value assigned by to , i.e.: Γ ( ) : At → {1, 0, U} where → ⊓{() | ∈ [ ]2}. We also need to define the reduct of given , i.e., = (At , , ) with: (i) At
1}, (ii) = ∩ (At ×
At ), and (ii) substituting every occurrence of in by . () = 0}/0] | ∈ At }, where [/ ] is obtained by = { ∈ At | (At) = = {[{ | Definition 1.
Let be an ADF with interpretation. Then, is admissible for if ≤ Γ ( ); is complete for if = Γ ( ); is preferred for if is ≤ -maximal among all admissible models; is grounded for if is ≤ -minimal among all complete models; and is stable if is a two-valued model of and { ∈ At | () = 1 } = { ∈ At | () = 1
} where is the grounded model of . We denote by 2V(), adm(), cmp(), prf(), grnd(), and stb() the sets of two-valued, admissible, complete, preferred, grounded, and stable models of . ∈ (At) a 3-valued cmp() ⊆ adm() as well as grnd() ⊆ cmp().
It was been shown that stb() ⊆ 2V() ⊆ prf() ⊆ Example 4 (Ex. 1 ctd.). The ADF in Ex. 1 has three complete models 1, 2, 3 with: 1() = 1, 1() = 0, 1() = 1 and 1( ) = 1; 2() = 0 and 3() = U for all ∈ At. An admissible model that is not complete is 4 with 4() = 1, 4() = 4() = 4( ) = U. 3 is the grounded model, whereas 1 and 2 are both preferred and two-valued, and only 2 is stable.
In this section, we recall Boolean networks as known from
the literature (see e.g., [
Definition 2. A regulatory graph is a directed graph = (V, ), where = {1, ..., } is the set of vertices (nodes) representing the regulatory compounds, and = {(, , ) : , ∈ , ∈ {+, − , ±}} is the set of signed edges representing the interactions between compounds.
An edge with = + is called positive interaction (or activation), representing that activates , while an edge with = − is called negative interaction (or inhibition), representing that inhibits . Occasionally, may (in combination with diferent compounds) both activate and inhibit another compound , which is represented with an edge with = ± . A node with no incoming edges is called input node, representing external stimuli, whose values do not change. Example 5. Fig. 2 shows regulatory graph = (V, ) with = {1, 2, 3, 4} and = {(1, 2, − ), (1, 3, +), (2, 1, +), (2, 3, +), (4, 2, +), (4, 3, − )}.
Boolean logical models then add regulatory functions for each compound to specify how diferent compounds that afect the same node interact with each other for that node’s activation.
Definition 3. A Boolean logical model of a regulatory network is defined as a tuple (V, ) where = {1, 2, ..., } is the set of variables representing the regulatory compounds of the network such that can be assigned to a value in {0, 1}, and = {1, 2, ..., } is the set of Boolean functions such that defines the value of and where = if is an input node.
Regulatory functions of input nodes may sometimes be omitted (cf. Fig. 2), which means that = , but commonly, we use the explicit representation.
Example 6. Fig. 2 presents a Boolean logical model with from Ex. 5 and regulatory functions for on the right.
We can observe that, syntactically, a Boolean network is strikingly similar to an abstract dialectical framework. The only diference is that, unlike the edges in the regulatory graph of a BN, links in ADFs commonly do not mention explicitly whether an argument is attacking or supporting. Still, this can be extracted from the corresponding acceptance conditions, and in some literature [20], the so-called polarity of links is explicitly represented (see also Section 3.3). Similarly, the exact representation of regulatory graphs difers in the literature. Using our notation here, we establish this connection between Boolean networks and ADFs formally.
Definition 4. Let = (, ) be a Boolean logical model of a regulatory network with regulatory graph = (, ). We define the corresponding ADF , = (, , ) with = {(, ) | (, , ) ∈ }.
Let = (At, , ) be an ADF. We define the corresponding Boolean logical model of a regulatory network as = (At, ). The corresponding regulatory graph = (At, ) can be obtained from in NNF with = {(, , +) | ∈ , ¬ ̸∈ } ∪ {(, , − ) | ¬ ∈ , ̸∈ } ∪ {(, , ± ) | ∈ , ¬ ∈ }.
The requirement for the acceptance conditions to be in Negation Normal Form (NNF) is necessary to include the correct edges in . Alternatively, one can determine the polarity using Definition 11 below. Either way, as we will see next, the semantics of Boolean networks is uniquely determined by the compounds and their Boolean functions, i.e., the Boolean logical model, and the regulatory graph can be left implicit. 3.2. Dynamics BNs allow us to capture the changes over time in a biological process based on the interactions of the various compounds involved, which should correctly represent the dynamics observable in the real system. We will see that the study of dynamics in BNs correspond to semantics of ADFs. We start with network states that are used to represent the (current) activations of a network’s compounds.
Definition 5. The network state of a BN with compounds is a vector = (1, ..., ) where is the value of the variable representing the -th compound of the network.
Clearly, for Boolean logical models, the number of diferent states in a network is given by 2. E.g., if nodes 1 and 3 in Ex. 6 are active and the other two are not, then the state will be represented by 1010. Similar representations are used for interpretations of ADFs (by ordering the atoms), and it is clear that the states in BNs correspond to possible world of ADFs.
The update of the i-th compound of a network from one discrete time point to the next is then defined as ( + 1) = (()) for state () at time , which clearly exactly corresponds to the evaluation of an acceptance condition in ADFs. We can then use state transition graphs [9] to describe how networks, and thus the modelled biological systems, evolve over time.
Definition 6. A State Transition Graph (STG) is a directed graph = (, ) where is the set of vertices representing the diferent states of the network, and is the set of edges representing the viable transitions between states according to given update scheme.
Two update schemes are employed to update the values of nodes in a BN: the synchronous and the asynchronous a) 0100 0000 updating scheme [10, 11]. Note that, given a Boolean logical model, the state transition graphs for the synchronous updating scheme and asynchronous updating scheme are uniquely determined.
In the synchronous updating scheme, at each time step, all compounds are updated simultaneously, i.e., given a state = (1, ..., ), the new state is obtained as ′ = (1(), ..., ()). Each network state has at most one successor (cf. Fig. 3.a), which is sometimes argued to be biologically less realistic and less accurate for analysis. Yet, synchronous updates are still regularly used [13], and many of the concepts below, such as trap spaces, are independent of the used scheme.
In the asynchronous updating scheme, at each time step, one or more regulatory functions may be applied [13]. This is closer to what is observable in real systems, since these changes seldomly tend to take place simultaneously. With n compounds in a network, and the frequently used, particular case of exactly one function being applied at each time step, each state can have at most possible state transitions (including a transition to itself - cf. Fig. 3.b).
There are certain cycles of states in which these networks reside most of the time. These cycles are a trap of sorts, since as soon as a network enters a cycle’s state, it is unable to exit the cycle. These traps, called attractors, are linked to many important cellular processes, such as phenotypes, cell cycle phases, cell growth, diferentiation, apoptosis, and more [14]. Because the number of states in a network is finite, transitions from all states eventually lead to an attractor. All states that lead to a certain attractor form its attraction basin.
Attractors have other relevant characteristics. One such characteristic is that, from any state belonging to an attractor, it is possible to find a path of attractor states to any other state in that attractor. Another important property is that there are no state transitions from attractor states to states outside of the attractor. Attractors can also be classified under diferent types. The left image of Fig. 3.a) shows an example of a stable state (or point attractor) in the whitecolored 0000 state. Stable states are attractors that contain only a single state. When that is not the case, the attractor is denoted as a cyclic (or complex) attractor, visualized in the right image of Fig. 3.a). There, we have a complex attractor comprised of four states: 0101, 1101, 1011 and 0011 [15]. Definition 7. Given an STG = (, ), a set ′ ⊆ is a trap set of if, for every ∈ ′, (, ′) ∈ implies ′ ∈ ′. An attractor is a ⊆ -minimal trap set. A stable state of is a singleton trap set of .
We obtain that stable states of a transition graph under synchronous update scheme coincide with the two-valued models of the corresponding ADF.
Proposition 1. Let be the synchronous state transition graph of the Boolean Model with regulatory graph , and , the corresponding ADF. Then, is a stable state of if is a two-valued model of ,.
To the best of our knowledge, the more general notion of a trap set has not been investigated in the context of ADFs. This is not surprising, as it has a clear meaning and use in biological networks, but not so much in argumentation: Example 7. Consider the ADF = ({, , }, , ) with = ¬, = ¬ and = ¬. Then {000, 111} is a trap set and an attractor, but their argumentative interpretation is not clear: if we interpret , , and as arguments that attack each other, the stability under transitions of {000, 111}, interesting in a biological interpretation, is of less interest in argumentation.
More surprisingly, we will now see that many other
semantics for ADFs have a natural counterpart in Boolean
networks. For example, there has been a lot of interest
in so-called subspaces of regulatory graphs [
Definition 8. A subspace of a regulatory graph (, ) is a mapping : ↦→ {0, 1, ⋆}. We call ∈ fixed if () ∈ {0, 1} and free if () = ⋆, and is the set of all fixed variables in . We let [] := { ∈ | ∀ ∈ : () = ()}.
We sometimes abuse notation and identify a subspace with its expanded variant [].
An interesting observation is that subspaces, interpreted as their representative set of Boolean valuations [], correspond exactly to the completions of the subspaces, interpreted as three-valued interpretations: There are three trap spaces: ⋆⋆, ⋆1, and 11. By Prop. 3, this corresponds to the interpretations UU and 11. However, the unique complete interpretation is 11.
We might conjecture that the complete interpretations correspond to the minimal trap spaces, but that is not the case either.
Example 9. Consider the ADF = ({}, , ) with = {}. There are three trap spaces: ⋆, 1, and 0. The corresponding interpretations U, 1 and 0 are not only admissible but also complete. However, U is not a minimal trap space.
We further note that there has been some interest in maximal and minimal trap spaces [15] in the literature on BNs. In more detail, trap sets are compared as follows: 1 ≤ 2 if [1] ⊆ [2]. It can be easily observed that this is the reverse of the information order ≤ known from ADFs:
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] ̸= , i.e., the trivial trap space is excluded by definition. Proposition 5. Let be a BN with regulatory graph , and , the corresponding ADF: is a minimal trap space of M if is preferred in ,.
However, maximal trap spaces do not correspond to the grounded model. The reason is that in BNs, the trivial trap space is excluded. E.g., in Ex. 3, 3 is the grounded model, but does not correspond to a maximal trap space as it is trivial trap space. Finally, we note that the concept of stable model from ADFs has no clear counterpart in BNs. Indeed, the main motivation behind stable models is to exclude self-supporting arguments (see e.g., Ex. 4 where 1 with supporting itself via = is excluded). In BNs, there is nothing a priori wrong with such self-supporting stable states, and it might often even have a clear biological meaning, e.g., since algae are self-reproducing. An interesting observation is that both the literature on ADFs and the literature on Boolean Networks has identified certain subclasses of frameworks for which the computational complexity of computational tasks decreases. In fact, both strands of literature have identified the same subclass! In the literature on ADFs, these frameworks are called bipolar ADFs, whereas in the literature on Boolean networks, they are called sign-definite .
Definition 10. A Boolean function : {0, 1} ↦→ {0, 1} is increasing monotone [decreasing monotone] on if (1, . . . , , . . . , ) ≤ (1, . . . , ′, . . . , ) [ (1, . . . , , . . . , ) ≥ (1, . . . , ′, . . . , )], where = 0 and ′ = 1. It is sign-definite if it is increasing or decreasing monotone for every = 1 . . . . A Boolean logical model (, ) is sign-definite if every Boolean function in is sign-definite.
It is well-known that a Boolean function is sign-definite if and only if it can be represented by a formula in disjunctive normal form in which all occurrences of a given literal are either negated or non-negated [18].
We now recall bipolar ADFs [19].
Definition 11. {0, 1}: • ≤ is supporting if (1, . . . , , . . . , ) = 1 implies (1, . . . , ′, . . . , ) = 1 where = 0 and ′ = 1, • ≤ is attacking if (1, . . . , , . . . , ) = 0 implies (1, . . . , ′, . . . , ) = 0 where = 0 and ′ = 1.
An ADF is bipolar if for every ∈ At, every ∈ par() is supporting, attacking or both in .
It was shown that an ADF is bipolar if every acceptance formula is equivalent to a formula that is syntactically bipolar, i.e., no atoms occurs both positively and negatively [20]. From this, we can show that these two special cases coincide: Corollary 1. A Boolean model is sign-definite if the corresponding ADF is bipolar.
Based on the established correspondence, we provide examples of insights from the literature on Boolean Networks that are directly relevant for ADFs. 4.1. Complexity of Counting Problems For many applications in KR, being able to know the number of solutions is important. For many formalisms, including abstract argumentation [21], according decision problems have been studied in depth. For ADFs, such a study is missing. Due to existing results from the literature on BNs we can start filling this gap.
For example, Bridoux et al. [22] study the complexity of deciding whether the number of stable states in a BN is above (or below) a given bound . Given the correspondence between BNs and ADFs established here, we immediately obtain the following corresponding results: Corollary 2. Deciding whether the maximal number of two-valued models in an ADF is larger or equal than is: in P for fixed = 1; NP-complete for fixed ≥ 2; NEXPTIME-complete for arbitrary ; and NP#P-complete for an arbitrary if the maximum in-degree of is bounded by a constant ≥ 2.
Deciding whether the minimal number of two-valued models in an ADF is smaller than is: NEXPTIMEcomplete for arbitrary without any bound on the indegree; NPNP-complete for fixed ≥ 2, if the maximum in-degree of is bounded by a constant ≥ 2; NP#Pcomplete for an arbitrary if the maximum in-degree of is bounded by a constant ≥ 2.2 4.2. Existence of Fixpoints There is a large line of work in the literature on Boolean networks that studies structural properties of Boolean networks that afect the existence (and the number) of fixed points. Such work immediately translates to the existence of twovalued models in ADFs. E.g., several works [23, 24, 25, 26] provide a theoretical analysis of the existence of fixpoints in sign-definite BN in relation to structural parameters of the corresponding Boolean networks. We follow Aracena [26] in defining a path in a BN as positive if the number of negative arcs is even, and negative otherwise.
The first few results study the connection between cycles, their parity, and the existence and number of fixpoints: Proposition 6. If a sign-definite BN has: no cycles, then it has a unique stable state [23]; no positive cycles, then it has at most one stable state [24]; no negative cycles, then it has at least one stable state [25]. If a BN has a strongly connected component such that all cycles of are negative and for each arc (, ) in the , ∈ then ∈ , then has no stable states [26].
Corollary 3. Let a bipolar ADF be given. Then: if has no cycles, then it has a unique two-valued model; if has no positive cycles, then it has at most one two-valued model; if has no negative cycles, then it has at least one twovalued model. If has a strongly connected component such that all cycles of are negative and for each arc (, ) in the , ∈ then ∈ , then has no two-valued models.
One finds also more intricate results on the existence of ifxpoints in the literature, for example in terms of so-called non-expansive maps, that guarantee the existence of stable states [27]. These fall outside the scope of this paper.
Some work has also investigated the connection between the existence of stable states and the structure of the corresponding BN: Proposition 7 ([26]). If a BN has at least one stable state, then it has at least one positive cycle.
Corollary 4. An ADF has a two-valued model has at least one positive cycle. 2The maximum in-degree of an ADF (At, , ) is the maximal number of diferent literals occurring in an acceptance formula ∈ .
The final result we discuss is an upper bound on the number of stable states in terms of the number of feedback vertex sets (FVSs). An FVS of a digraph = (, ) is defined to be a set of vertices that contains at least one vertex of each cycle of . The minimum number of vertices of a FVS is denoted by ().
Proposition 8 ([26]). A Boolean logical model = (, ), where | − ()| ≥ 1 for all ∈ , has at most 2 () stable states.
Corollary 5. An ADF = (At, , ) s.t. every argument has at least one attacker has at most 2 ((At,)) stable states.
We have reviewed the main syntactic similarities between ADFs and BNs, and demonstrated that these extend in large parts to the semantical level. Furthermore, we have shown the fruitfulness of this connection by deriving results on complexity and existence of semantics for ADFs based on existing results for BNs. We hope that our results will lead to further cross-contamination between these two fields, such as the use of implementations or benchmarks. Acknowledgments We thank the anonymous reviewers for their valuable feedback. This work is partially supported by project BIO-REVISE (2023.13327.PEX) and NOVA LINCS ref. UIDB/04516/2020 (https://doi.org/10.54499/UIDB/04516/ 2020) and ref. UIDP/04516/2020 (https://doi.org/10.54499/ UIDP/04516/2020) with the financial support of FCT. [9] A. Naldi, E. Remy, D. Thiefry, C. Chaouiya, Dynamically consistent reduction of logical regulatory graphs, Theor. Comput. Sci. 412 (2011) 2207–2218. [10] A. Faure, A. Naldi, C. Chaouiya, D. Thiefry, Dynamical 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 Models 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 symbolic 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 complexity of minimal trap spaces in boolean networks, arXiv preprint arXiv:2212.12756 (2022). [17] J. Heyninck, G. Kern-Isberner, An epistemic interpretation 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, Complexity 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 automates cellulaires contractants, Linear Algebra and its applications 29 (1980) 393–412. [24] É. Remy, P. Ruet, D. Thiefry, Graphic requirements for multistability and attractive cycles in a boolean dynamical framework, Advances in Applied Mathematics 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 regulatory 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. Proposition 1. Let be the synchronous state transition graph of the Boolean Model with regulatory graph , and , the corresponding ADF. Then, is a stable state of if is a two-valued model of ,. Proof. This follows from the following list of equivalences: is a stable state for the synchronous transition graph of = (, ) ⇔ = () for every ∈ At ⇔ () = () for every ∈ At ⇔ is a two-valued model of .
Proposition 2. Let be a subspace , and : ↦→ {0, 1, U} defined by {︃() (2)
Proof. With Proposition 3, is a trap space of M if is admissible in ,. Suppose now towards a contradiction that is a minimal trap space, yet is not preferred, i.e. there is some admissible with < . Then with Proposition 4 and Proposition 3, there is a trap space < , contradicting being a minimal trap space.
The reader might be somewhat surprised by the fact that links can be both attacking and supporting. However, the only possibility for that being the case, is if the link is redundant: Proposition 10. Consider an ADF = (At, , ) with 1, 2 ∈ At and 2 being supporting and attacking in 1 . For every 1, 2 ∈ 2(At) s.t. 1(2) ̸= 2(2) and 1() = 2() for every ∈ At, Γ (1)(1) = Γ (1)(1).
Corollary 1. A Boolean model is sign-definite if the corresponding ADF is bipolar.
Proof. We first recall that, given a formula , the polarity of an atom in is determined by the number of negations on the path from the root of the formula tree to the atom, and is positive if this number is even, and negative otherwise. For example, in ¬( ∧ ¬), occurs negatively and occurs positively. A propositional formula is syntactically bipolar if no atom occurs both positively and negatively in .
Clearly, an acceptance condition is supporting respectively attacking if it is increasing respectively decreasing monotone. The rest of the proof is an immediate consequence of [20, Theorem 1], which implies that an ADF = (At, , ) is bipolar if, for every ∈ At, is syntactically bipolar.
Proposition 3. Let be a Boolean Model with regulatory graph , and , the corresponding ADF: is a trap space of M if is admissible in ,.
Proof. We first need some preliminaries due to Klarner et
al. [
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 = ⋀︀=1 ⋁︀ ∆ . Then [] = ⋀︀=1 ⋁︀ (∆ ) where (∆) is obtained by replacing every occurrence of some ∈ by (). Suppose now []() = 0. This Tmheuasn,s⊓th{ere(⋁i︀s∆ so)me| =∈ 1[ , ..].2,}2=s.t.0 w(∆ hic)h =imp{li0e}s. that ⊓{(⋀︀=1 ⋁︀ ∆ ) | ∈ [ ] } = 0. The cases for []() = 1 and []() = ⋆ are similar. Proof. With Proposition 2 from [17], 2 ≤ 1 if for every ∈ At if [ 2 ]2 ⊇ [ 1 ]2. As [] = [ ]2 for = 1, 2 (Proposition 2), we obtain that 2 ≤ 1 if [1] ⊆ [2]. By definition of ≤ , 2 ≤ 1 if 1 ≤ 2.