Scalable Counting of Minimal Trap Spaces and Fixed Points in Boolean Networks
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F25%3A00143666" target="_blank" >RIV/00216224:14330/25:00143666 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.4230/LIPIcs.CP.2025.17" target="_blank" >http://dx.doi.org/10.4230/LIPIcs.CP.2025.17</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.CP.2025.17" target="_blank" >10.4230/LIPIcs.CP.2025.17</a>
Alternative languages
Result language
angličtina
Original language name
Scalable Counting of Minimal Trap Spaces and Fixed Points in Boolean Networks
Original language description
Boolean Networks (BNs) serve as a fundamental modeling framework for capturing complex dynamical systems across various domains, including systems biology, computational logic, and artificial intelligence. A crucial property of BNs is the presence of trap spaces - subspaces of the state space that, once entered, cannot be exited. Minimal trap spaces, in particular, play a significant role in analyzing the long-term behavior of BNs, making their efficient enumeration and counting essential. The fixed points in BNs are a special case of minimal trap spaces. In this work, we formulate several meaningful counting problems related to minimal trap spaces and fixed points in BNs. These problems provide valuable insights both within BN theory (e.g., in probabilistic reasoning and dynamical analysis) and in broader application areas, including systems biology, abstract argumentation, and logic programming. To address these computational challenges, we propose novel methods based on approximate answer set counting, leveraging techniques from answer set programming. Our approach efficiently approximates the number of minimal trap spaces and the number of fixed points without requiring exhaustive enumeration, making it particularly well-suited for large-scale BNs. Our experimental evaluation on an extensive and diverse set of benchmark instances shows that our methods significantly improve the feasibility of counting minimal trap spaces and fixed points, paving the way for new applications in BN analysis and beyond.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
—
Continuities
S - Specificky vyzkum na vysokych skolach
Others
Publication year
2025
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
31ST INTERNATIONAL CONFERENCE ON PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING, CP 2025
ISBN
9783959773805
ISSN
1868-8969
e-ISSN
—
Number of pages
26
Pages from-to
1-26
Publisher name
SCHLOSS DAGSTUHL, LEIBNIZ CENTER INFORMATICS
Place of publication
Dagstuhl, Germany
Event location
GLASGOW, SCOTLAND
Event date
Aug 10, 2025
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
001590355100017