• Classified by Research Topic • Sorted by Date • Classified by Publication Type •
ApproxASP - A Scalable Approximate Answer Set Counter.
Mohimenul Kabir, Flavio Everardo, Ankit K. Shukla, Markus Hecher, Johannes Fichte and Kuldeep S. Meel.
In Proceedings of AAAI Conference on Artificial Intelligence (AAAI), February 2022.
Answer Set Programming (ASP) is a framework in artificial intelligence and knowledge representation for declarative modeling and problem solving. Modern ASP solvers focus on the computation or enumeration of answer sets. However, a variety of probabilistic applications in reasoning or logic programming require counting answer sets. While counting can be done by enumeration, simple enumeration becomes immediately infeasible if the number of solutions is high. On the other hand, approaches to exact counting are of high worst-case complexity. In fact, in propositional model counting, exact counting becomes impractical. In this work, we present a scalable approach to approximate counting for answer set programming. Our approach is based on systematically adding XOR constraints to ASP programs, which divide the search space. We prove that adding random XOR constraints partitions the answer sets of an ASP program. In practice, we use a Gaussian elimination-based approach by lifting ideas from SAT to ASP and integrating it into a state of the art ASP solver, which we call ApproxASP. Finally, our experimental evaluation shows the scalability of our approach over the existing ASP systems.
@inproceedings{KESHFM22,
title={ApproxASP - A Scalable Approximate Answer Set Counter},
author={
Kabir, Mohimenul and Everardo, Flavio and
Shukla, Ankit K. and Hecher, Markus and Fichte, Johannes and Meel, Kuldeep
S.
},
booktitle=AAAI,
month=feb,
year={2022},
bib2html_rescat={Counting},
bib2html_dl_pdf={../Papers/aaai22-keskhm.pdf},
bib2html_pubtype={Refereed Conference},
abstract={
Answer Set Programming (ASP) is a framework in artificial intelligence and
knowledge representation for declarative modeling and problem solving.
Modern ASP solvers focus on the computation or enumeration of answer sets.
However, a variety of probabilistic applications in reasoning or logic
programming require counting answer sets. While counting can be done by
enumeration, simple enumeration becomes immediately infeasible if the number
of solutions is high. On the other hand, approaches to exact counting are of
high worst-case complexity. In fact, in propositional model counting, exact
counting becomes impractical. In this work, we present a scalable approach
to approximate counting for answer set programming. Our approach is based on
systematically adding XOR constraints to ASP programs, which divide the
search space. We prove that adding random XOR constraints partitions the
answer sets of an ASP program. In practice, we use a Gaussian
elimination-based approach by lifting ideas from SAT to ASP and integrating
it into a state of the art ASP solver, which we call ApproxASP. Finally, our
experimental evaluation shows the scalability of our approach over the
existing ASP systems.
},
}
Generated by bib2html.pl (written by Patrick Riley with layout from Sanjit A. Seshia ) on Tue Apr 28, 2026 01:27:21