Lilian Salinas
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Lilian Salinas has a total of 15 co-authors. Here are the top co-authors by number of shared publications:
- Julio Aracena
Universidad de Concepción
4 shared publications - Adrien Richard
Université Côte d'Azur, Sophia Antipolis, France
2 shared publications - Adrien Richard
Sophia Antipolis. Department of Computer Sciences Partially supported by CNRS project PICS06718 University of Nice CI
2 shared publications - Alexis Poindron
ENSTA, Unité d’Économie Appliquée, Paris, France
2 shared publications - Florian Bridoux
Normandie Univ, UNICAEN, ENSICAEN, CNRS, GREYC, Caen, France
2 shared publications Julio Aracena
2 shared publications
Latest Publications
- Open Access
- 18 June 2026
- Published by Elsevier in SSRN Electronic Journal
Compatibility of unate Boolean functions via coverage vectors
In Boolean models of gene regulatory networks, each regulator acts as an activator or a repressor, a structure captured by unate Boolean functions. Determining whether a unate Boolean function is compatible with a set of binary observations is NP-complete. We address this problem through a combinatorial formulation built on two concepts: the multiset of discrepancies, which encodes how positive and negative observations differ, and the coverage vector, which represents a way to resolve those differences. We prove that the existence of a coverage vector is necessary and sufficient for the existence of a compatible unate function, and we characterize the full set of compatible functions as an interval between two explicit bounds. Building on these results, we develop a greedy randomized algorithm that constructs coverage vectors and scales to instances with several thousand variables. Experiments on synthetic data show that recovery of the true signed support depends primarily on the ratio between active and total variables, and that an optional sparsity bound improves both recall and precision. A case study on the Drosophila ventral furrow Boolean network confirms the applicability of the method to gene regulatory networks under sparse biological observations.
- 18 June 2026
- Published by Elsevier in SSRN Electronic Journal
Open AccessCompatibility of unate Boolean functions via coverage vectors
In Boolean models of gene regulatory networks, each regulator acts as an activator or a repressor, a structure captured by unate Boolean functions. Determining whether a unate Boolean function is compatible with a set of binary observations is NP-complete. We address this problem through a combinatorial formulation built on two concepts: the multiset of discrepancies, which encodes how positive and negative observations differ, and the coverage vector, which represents a way to resolve those differences. We prove that the existence of a coverage vector is necessary and sufficient for the existence of a compatible unate function, and we characterize the full set of compatible functions as an interval between two explicit bounds. Building on these results, we develop a greedy randomized algorithm that constructs coverage vectors and scales to instances with several thousand variables. Experiments on synthetic data show that recovery of the true signed support depends primarily on the ratio between active and total variables, and that an optional sparsity bound improves both recall and precision. A case study on the Drosophila ventral furrow Boolean network confirms the applicability of the method to gene regulatory networks under sparse biological observations.
- Open Access
- 18 June 2026
- Published by Elsevier in SSRN Electronic Journal
Compatibility of unate Boolean functions via coverage vectors
In Boolean models of gene regulatory networks, each regulator acts as an activator or a repressor, a structure captured by unate Boolean functions. Determining whether a unate Boolean function is compatible with a set of binary observations is NP-complete. We address this problem through a combinatorial formulation built on two concepts: the multiset of discrepancies, which encodes how positive and negative observations differ, and the coverage vector, which represents a way to resolve those differences. We prove that the existence of a coverage vector is necessary and sufficient for the existence of a compatible unate function, and we characterize the full set of compatible functions as an interval between two explicit bounds. Building on these results, we develop a greedy randomized algorithm that constructs coverage vectors and scales to instances with several thousand variables. Experiments on synthetic data show that recovery of the true signed support depends primarily on the ratio between active and total variables, and that an optional sparsity bound improves both recall and precision. A case study on the Drosophila ventral furrow Boolean network confirms the applicability of the method to gene regulatory networks under sparse biological observations.
- 18 June 2026
- Published by Elsevier in SSRN Electronic Journal
Open AccessCompatibility of unate Boolean functions via coverage vectors
In Boolean models of gene regulatory networks, each regulator acts as an activator or a repressor, a structure captured by unate Boolean functions. Determining whether a unate Boolean function is compatible with a set of binary observations is NP-complete. We address this problem through a combinatorial formulation built on two concepts: the multiset of discrepancies, which encodes how positive and negative observations differ, and the coverage vector, which represents a way to resolve those differences. We prove that the existence of a coverage vector is necessary and sufficient for the existence of a compatible unate function, and we characterize the full set of compatible functions as an interval between two explicit bounds. Building on these results, we develop a greedy randomized algorithm that constructs coverage vectors and scales to instances with several thousand variables. Experiments on synthetic data show that recovery of the true signed support depends primarily on the ratio between active and total variables, and that an optional sparsity bound improves both recall and precision. A case study on the Drosophila ventral furrow Boolean network confirms the applicability of the method to gene regulatory networks under sparse biological observations.
- 29 June 2023
- Published by Springer Nature in Natural Computing
- Vol. 22 (3) , 411-429
Complexity of limit cycles with block-sequential update schedules in conjunctive networks
- 29 June 2023
- Published by Springer Nature in Natural Computing
- Vol. 22 (3) , 411-429
Complexity of limit cycles with block-sequential update schedules in conjunctive networks
- 18 April 2023
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 136, 249-279
Synchronizing Boolean networks asynchronously
- 18 April 2023
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 136, 249-279
Synchronizing Boolean networks asynchronously
- Open Access
Synchronizing Boolean networks asynchronously
The {\em asynchronous automaton} associated with a Boolean network $f:\{0,1\}^n\to\{0,1\}^n$, considered in many applications, is the finite deterministic automaton where the set of states is $\{0,1\}^n$, the alphabet is $[n]$, and the action of letter $i$ on a state $x$ consists in either switching the $i$th component if $f_i(x)\neq x_i$ or doing nothing otherwise. These actions are extended to words in the natural way. A word is then {\em synchronizing} if the result of its action is the same for every state. In this paper, we ask for the existence of synchronizing words, and their minimal length, for a basic class of Boolean networks called and-or-nets: given an arc-signed digraph $G$ on $[n]$, we say that $f$ is an {\em and-or-net} on $G$ if, for every $i\in [n]$, there is $a$ such that, for all state $x$, $f_i(x)=a$ if and only if $x_j=a$ ($x_j\neq a$) for every positive (negative) arc from $j$ to $i$; so if $a=1$ ($a=0$) then $f_i$ is a conjunction (disjunction) of positive or negative literals. Our main result is that if $G$ is strongly connected and has no positive cycles, then either every and-or-net on $G$ has a synchronizing word of length at most $10(\sqrt{5}+1)^n$, much smaller than the bound $(2^n-1)^2$ given by the well known \v{C}ern\'y's conjecture, or $G$ is a cycle and no and-or-net on $G$ has a synchronizing word. This contrasts with the following complexity result: it is coNP-hard to decide if every and-or-net on $G$ has a synchronizing word, even if $G$ is strongly connected or has no positive cycles.Open AccessSynchronizing Boolean networks asynchronously
The {\em asynchronous automaton} associated with a Boolean network $f:\{0,1\}^n\to\{0,1\}^n$, considered in many applications, is the finite deterministic automaton where the set of states is $\{0,1\}^n$, the alphabet is $[n]$, and the action of letter $i$ on a state $x$ consists in either switching the $i$th component if $f_i(x)\neq x_i$ or doing nothing otherwise. These actions are extended to words in the natural way. A word is then {\em synchronizing} if the result of its action is the same for every state. In this paper, we ask for the existence of synchronizing words, and their minimal length, for a basic class of Boolean networks called and-or-nets: given an arc-signed digraph $G$ on $[n]$, we say that $f$ is an {\em and-or-net} on $G$ if, for every $i\in [n]$, there is $a$ such that, for all state $x$, $f_i(x)=a$ if and only if $x_j=a$ ($x_j\neq a$) for every positive (negative) arc from $j$ to $i$; so if $a=1$ ($a=0$) then $f_i$ is a conjunction (disjunction) of positive or negative literals. Our main result is that if $G$ is strongly connected and has no positive cycles, then either every and-or-net on $G$ has a synchronizing word of length at most $10(\sqrt{5}+1)^n$, much smaller than the bound $(2^n-1)^2$ given by the well known \v{C}ern\'y's conjecture, or $G$ is a cycle and no and-or-net on $G$ has a synchronizing word. This contrasts with the following complexity result: it is coNP-hard to decide if every and-or-net on $G$ has a synchronizing word, even if $G$ is strongly connected or has no positive cycles. - 20 April 2022
- Published by Springer Nature
- p. 233-252
Existence and Non Existence of Limit Cycles in Boolean Networks
- 20 April 2022
- Published by Springer Nature
- p. 233-252
Existence and Non Existence of Limit Cycles in Boolean Networks
- Open Access
Complexity of limit cycles with block-sequential update schedules in conjunctive networks
In this paper, we deal the following decision problem: given a conjunctive Boolean network defined by its interaction digraph, does it have a limit cycle of a given length k? We prove that this problem is NP-complete in general if k is a parameter of the problem and in P if the interaction digraph is strongly connected. The case where $k$ is a constant, but the interaction digraph is not strongly connected remains open. Furthermore, we study the variation of the decision problem: given a conjunctive Boolean network, does there exist a block-sequential (resp. sequential) update schedule such that there exists a limit cycle of length k? We prove that this problem is NP-complete for any constant k >= 2.Open AccessComplexity of limit cycles with block-sequential update schedules in conjunctive networks
In this paper, we deal the following decision problem: given a conjunctive Boolean network defined by its interaction digraph, does it have a limit cycle of a given length k? We prove that this problem is NP-complete in general if k is a parameter of the problem and in P if the interaction digraph is strongly connected. The case where $k$ is a constant, but the interaction digraph is not strongly connected remains open. Furthermore, we study the variation of the decision problem: given a conjunctive Boolean network, does there exist a block-sequential (resp. sequential) update schedule such that there exists a limit cycle of length k? We prove that this problem is NP-complete for any constant k >= 2. - Open Access
Number of fixed points and disjoint cycles in monotone Boolean networks
Given a digraph $G$, a lot of attention has been deserved on the maximum number $\phi(G)$ of fixed points in a Boolean network $f:\{0,1\}^n\to\{0,1\}^n$ with $G$ as interaction graph. In particular, a central problem in network coding consists in studying the optimality of the classical upper bound $\phi(G)\leq 2^{\tau}$, where $\tau$ is the minimum size of a feedback vertex set of $G$. In this paper, we study the maximum number $\phi_m(G)$ of fixed points in a {\em monotone} Boolean network with interaction graph $G$. We establish new upper and lower bounds on $\phi_m(G)$ that depends on the cycle structure of $G$. In addition to $\tau$, the involved parameters are the maximum number $\nu$ of vertex-disjoint cycles, and the maximum number $\nu^{*}$ of vertex-disjoint cycles verifying some additional technical conditions. We improve the classical upper bound $2^\tau$ by proving that $\phi_m(G)$ is at most the largest sub-lattice of $\{0,1\}^\tau$ without chain of size $\nu+1$, and without another forbidden-pattern of size $2\nu^{*}$. Then, we prove two optimal lower bounds: $\phi_m(G)\geq \nu+1$ and $\phi_m(G)\geq 2^{\nu^{*}}$. As a consequence, we get the following characterization: $\phi_m(G)=2^\tau$ if and only if $\nu^{*}=\tau$. As another consequence, we get that if $c$ is the maximum length of a chordless cycle of $G$ then $2^{\nu/3^c}\leq\phi_m(G)\leq 2^{c\nu}$. Finally, with the technics introduced, we establish an upper bound on the number of fixed points of any Boolean network according to its signed interaction graph.Open AccessNumber of fixed points and disjoint cycles in monotone Boolean networks
Given a digraph $G$, a lot of attention has been deserved on the maximum number $\phi(G)$ of fixed points in a Boolean network $f:\{0,1\}^n\to\{0,1\}^n$ with $G$ as interaction graph. In particular, a central problem in network coding consists in studying the optimality of the classical upper bound $\phi(G)\leq 2^{\tau}$, where $\tau$ is the minimum size of a feedback vertex set of $G$. In this paper, we study the maximum number $\phi_m(G)$ of fixed points in a {\em monotone} Boolean network with interaction graph $G$. We establish new upper and lower bounds on $\phi_m(G)$ that depends on the cycle structure of $G$. In addition to $\tau$, the involved parameters are the maximum number $\nu$ of vertex-disjoint cycles, and the maximum number $\nu^{*}$ of vertex-disjoint cycles verifying some additional technical conditions. We improve the classical upper bound $2^\tau$ by proving that $\phi_m(G)$ is at most the largest sub-lattice of $\{0,1\}^\tau$ without chain of size $\nu+1$, and without another forbidden-pattern of size $2\nu^{*}$. Then, we prove two optimal lower bounds: $\phi_m(G)\geq \nu+1$ and $\phi_m(G)\geq 2^{\nu^{*}}$. As a consequence, we get the following characterization: $\phi_m(G)=2^\tau$ if and only if $\nu^{*}=\tau$. As another consequence, we get that if $c$ is the maximum length of a chordless cycle of $G$ then $2^{\nu/3^c}\leq\phi_m(G)\leq 2^{c\nu}$. Finally, with the technics introduced, we establish an upper bound on the number of fixed points of any Boolean network according to its signed interaction graph. - Open Access
Fixed points in conjunctive networks and maximal independent sets in graph contractions
Given a graph $G$, viewed as a loop-less symmetric digraph, we study the maximum number of fixed points in a conjunctive boolean network with $G$ as interaction graph. We prove that if $G$ has no induced $C_4$, then this quantity equals both the number of maximal independent sets in $G$ and the maximum number of maximal independent sets among all the graphs obtained from $G$ by contracting some edges. We also prove that, in the general case, it is coNP-hard to decide if one of these equalities holds, even if $G$ has a unique induced $C_4$.Open AccessFixed points in conjunctive networks and maximal independent sets in graph contractions
Given a graph $G$, viewed as a loop-less symmetric digraph, we study the maximum number of fixed points in a conjunctive boolean network with $G$ as interaction graph. We prove that if $G$ has no induced $C_4$, then this quantity equals both the number of maximal independent sets in $G$ and the maximum number of maximal independent sets among all the graphs obtained from $G$ by contracting some edges. We also prove that, in the general case, it is coNP-hard to decide if one of these equalities holds, even if $G$ has a unique induced $C_4$. - 8 February 2017
- Published by Springer Nature
- p. 273-281
Chloridizing Roasting of Bismuthinite with Sodium Chloride–Oxygen
- 8 February 2017
- Published by Springer Nature
- p. 273-281
Chloridizing Roasting of Bismuthinite with Sodium Chloride–Oxygen