Author name cluster

Mohimenul Kabir

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

2 author rows

AAAI Conference 2024 Conference Paper

Exact ASP Counting with Compact Encodings

Mohimenul Kabir
Supratik Chakraborty
Kuldeep S. Meel

Answer Set Programming (ASP) has emerged as a promising paradigm in knowledge representation and automated reason- ing owing to its ability to model hard combinatorial problems from diverse domains in a natural way. Building on advances in propositional SAT solving, the past two decades have wit- nessed the emergence of well-engineered systems for solv- ing the answer set satisfiability problem, i.e., finding mod- els or answer sets for a given answer set program. In re- cent years, there has been growing interest in problems be- yond satisfiability, such as model counting, in the context of ASP. Akin to the early days of propositional model count- ing, state-of-the-art exact answer set counters do not scale well beyond small instances. Exact ASP counters struggle with handling larger input formulas. The primary contribu- tion of this paper is a new ASP counting framework, called sharpASP, which counts answer sets avoiding larger input formulas. This relies on an alternative way of defining answer sets that allows lifting of key techniques developed in the con- text of propositional model counting. Our extensive empirical analysis over 1470 benchmarks demonstrates significant per- formance gain over current state-of-the-art exact answer set counters. Specifically, by using sharpASP, we were able to solve 1062 benchmarks with PAR2 score of 3082 whereas using prior state-of-the-art, we could only solve 895 bench- marks with PAR2 score of 4205, all other experimental con- ditions being the same.

PDF Details DOI

LPAR Conference 2023 Conference Paper

A Fast and Accurate ASP Counting Based Network Reliability Estimator

Mohimenul Kabir
Kuldeep S. Meel

The quantification of system reliability is fundamental to the assessment of a system’s safety and resilience, and has been of interest to decision-makers. Since quantifying the system reliability is shown to be computationally intractable, researchers aim to find approximations. Existing approaches to approximate reliability either suffer from poor scalability or lack of correctness guarantees. Answer Set Programming (ASP) is a powerful tool for knowledge representation that can specify complex combinatorial problems. In recent years, the new applications of ASP have propelled the emergence of well-engineered ASP systems. This paper proposes a new ASP counting based framework, RelNet-ASP, to approximate or estimate the reliability of a system or network. The framework reduces the problem of reliability estimation to an approximate model counting problem on ASP programs, offering formal guarantees of the estimated reliability. The experimental evaluation demonstrates that RelNet-ASP outperforms state-of-the-art techniques in terms of both runtime performance and accuracy.

Details

AAAI Conference 2022 Conference Paper

ApproxASP – a Scalable Approximate Answer Set Counter

Mohimenul Kabir
Flavio O Everardo
Ankit K Shukla
Markus Hecher
Johannes Klaus Fichte
Kuldeep S Meel

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 ASP. Our approach is based on systematically adding parity (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 eliminationbased approach by lifting ideas from SAT to ASP and integrate it into a state of the art ASP solver, which we call ApproxASP. Finally, our experimental evaluation shows the scalability of our approach over existing ASP systems.

PDF Details