• Classified by Research Topic • Sorted by Date • Classified by Publication Type •
On Lower Bounding Minimal Model Count.
Mohimenul Kabir, and Kuldeep S. Meel.
In Proceedings of the International Conference on Logic Programming (ICLP), November 2024.
Best Paper Award
Minimal models of a Boolean formula play a pivotal role in various reasoning tasks. While previous research has primarily focused on qualitative analysis over minimal models; our study concentrates on the quantitative aspect, specifically counting of minimal models. Exact counting of minimal models is strictly harder than #P, prompting our investigation into establishing a lower bound for their quantity, which is often useful in related applications. In this paper, we introduce two novel techniques for counting minimal models, leveraging the expressive power of answer set programming: the first technique employs methods from knowledge compilation, while the second one draws on recent advancements in hashing-based approximate model counting. Through empirical evaluations, we demonstrate that our methods significantly improve the lower bound estimates of the number of minimal models, surpassing the performance of existing minimal model reasoning systems in terms of runtime.
@inproceedings{km24,
title={On Lower Bounding Minimal Model Count},
abstract={
Minimal models of a Boolean formula play a pivotal role in various reasoning
tasks. While
previous research has primarily focused on qualitative analysis over minimal
models; our study
concentrates on the quantitative aspect, specifically counting of minimal
models. Exact counting
of minimal models is strictly harder than #P, prompting our investigation
into establishing a
lower bound for their quantity, which is often useful in related
applications. In this paper, we
introduce two novel techniques for counting minimal models, leveraging the
expressive power of
answer set programming: the first technique employs methods from knowledge
compilation, while
the second one draws on recent advancements in hashing-based approximate
model counting.
Through empirical evaluations, we demonstrate that our methods significantly
improve the
lower bound estimates of the number of minimal models, surpassing the
performance of existing
minimal model reasoning systems in terms of runtime.
},
author={Kabir, Mohimenul and Meel, Kuldeep S.},
year={2024},
booktitle=ICLP,
month=nov,
bib2html_rescat={Counting},
bib2html_pubtype={Refereed Conference,Award Winner},
note={Best Paper Award},
bib2html_dl_pdf={https://arxiv.org/pdf/2407.09744},
}
Generated by bib2html.pl (written by Patrick Riley with layout from Sanjit A. Seshia ) on Tue Apr 28, 2026 01:27:21