• 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.
Minimal models of a Boolean formula play a pivotal role in various reasoning tasks. Whileprevious research has primarily focused on qualitative analysis over minimal models; our studyconcentrates on the quantitative aspect, specifically counting of minimal models. Exact countingof minimal models is strictly harder than #P, prompting our investigation into establishing alower bound for their quantity, which is often useful in related applications. In this paper, weintroduce two novel techniques for counting minimal models, leveraging the expressive power ofanswer set programming: the first technique employs methods from knowledge compilation, whilethe second one draws on recent advancements in hashing-based approximate model counting.Through empirical evaluations, we demonstrate that our methods significantly improve thelower bound estimates of the number of minimal models, surpassing the performance of existingminimal 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},
bib2html_dl_pdf={https://arxiv.org/pdf/2407.09744},
}
Generated by bib2html.pl (written by Patrick Riley with layout from Sanjit A. Seshia ) on Thu Aug 22, 2024 18:37:34