• Classified by Research Topic • Sorted by Date • Classified by Publication Type •
Scalable Counting of Minimal Trap Spaces and Fixed Points in Boolean Networks .
Mohimenul Kabir, Van-Giang Trinh, Samuel Pastva and Kuldeep S. Meel.
In Proceedings of International Conference on Constraint Programming (CP), pp. 17:1–17:26, 2025.
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.
@inproceedings{KabirTPM25CP,
title={
Scalable Counting of Minimal Trap Spaces and Fixed Points in Boolean
Networks
},
author={
Kabir, Mohimenul and Trinh, Van-Giang and Pastva, Samuel and Meel, Kuldeep
S.
},
booktitle=CP,
pages={17:1--17:26},
year={2025},
bib2html_rescat={Counting},
bib2html_pubtype={Refereed Conference},
bib2html_dl_pdf={https://doi.org/10.4230/LIPIcs.CP.2025.17},
abstract={
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.
},
}
Generated by bib2html.pl (written by Patrick Riley with layout from Sanjit A. Seshia ) on Tue Apr 28, 2026 01:27:21