Computational complexity of minimal trap spaces in Boolean networks
DOI10.1137/23m1553248MaRDI QIDQ6633132
Loïc Paulevé, Kangbok Lee, Kyungduk Moon
Publication date: 5 November 2024
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
computational complexityattractorssystem dynamicsautomata networktrap spaceBoolean function representation
Dynamical systems in biology (37N25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Switching theory, applications of Boolean algebras to circuits and networks (94C11) Computational aspects of satisfiability (68R07) Computational methods for attractors of dynamical systems (37M22)
Cites Work
- Unnamed Item
- A model of influence based on aggregation functions
- Petri net representation of multi-valued logical regulatory graphs
- Combinatorics on update digraphs in Boolean networks
- Positive circuits and maximal number of fixed points in discrete dynamical systems
- The polynomial-time hierarchy
- BDDs -- design, analysis, complexity, and applications.
- On the computational cost of disjunctive logic programming: Propositional case
- Computing maximal and minimal trap spaces of Boolean networks
- A general model of binary opinions updating
- On simulation in automata networks
- Minimal trap spaces of logical models are maximal siphons of their Petri net encoding
- Bilevel integer programming on a Boolean network for discovering critical genetic alterations in cancer development and therapy
- On the Tractable Counting of Theory Models and its Application to Truth Maintenance and Belief Revision
- Algorithms for Analysis, Inference, and Control of Boolean Networks
- Computational Complexity
- Static Analysis of Boolean Networks Based on Interaction Graphs: A Survey
- Depth-First Search and Linear Graph Algorithms
- Trap spaces of Boolean networks are conflict-free siphons of their Petri net encoding
- Tackling universal properties of minimal trap spaces of Boolean networks
- Non-deterministic updates of Boolean networks
This page was built for publication: Computational complexity of minimal trap spaces in Boolean networks
