Author name cluster

Rafael Kiesel

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.

8 papers

2 author rows

AIJ Journal 2024 Journal Article

aspmc: New frontiers of algebraic answer set counting

Thomas Eiter
Markus Hecher
Rafael Kiesel

In the last decade, there has been increasing interest in extensions of answer set programming (ASP) that cater for quantitative information such as weights or probabilities. A wide range of quantitative reasoning tasks for ASP and logic programming, among them probabilistic inference and parameter learning in the neuro-symbolic setting, can be expressed as algebraic answer set counting (AASC) tasks, i. e. , weighted model counting for ASP with weights calculated over some semiring, which makes efficient solvers for AASC desirable. In this article, we present Image 1, a new solver for AASC that pushes the limits of efficient solvability. Notably, Image 1 provides improved performance compared to the state of the art in probabilistic inference by exploiting three insights gained from thorough theoretical investigations in our work. Namely, we consider the knowledge compilation step in the AASC pipeline, where the underlying logical theory specified by the answer set program is converted into a tractable circuit representation, on which AASC is feasible in polynomial time. First, we provide a detailed comparison of different approaches to knowledge compilation for programs, revealing that translation to propositional formulas followed by compilation to sd-DNNF seems favorable. Second, we study how the translation to propositional formulas should proceed to result in efficient compilation. This leads to the second and third insight, namely a novel way of breaking the positive cyclic dependencies in a program, called T P -Unfolding, and an improvement to the Clark Completion, the procedure used to transform programs without positive cyclic dependencies into propositional formulas. Both improvements are tailored towards efficient knowledge compilation. Our empirical evaluation reveals that while all three advancements contribute to the success of Image 1, T P -Unfolding improves performance significantly by allowing us to handle cyclic instances better.

Details DOI

AAAI Conference 2024 Conference Paper

On the Structural Hardness of Answer Set Programming: Can Structure Efficiently Confine the Power of Disjunctions?

Markus Hecher
Rafael Kiesel

Answer Set Programming (ASP) is a generic problem modeling and solving framework with a strong focus on knowledge representation and a rapid growth of industrial applications. So far, the study of complexity resulted in characterizing hardness and determining their sources, fine-grained insights in the form of dichotomy-style results, as well as detailed parameterized complexity landscapes. Unfortunately, for the well-known parameter treewidth disjunctive programs require double-exponential runtime under reasonable complexity assumptions. This quickly becomes out of reach. We deal with the classification of structural parameters for disjunctive ASP on the program's rule structure (incidence graph). First, we provide a polynomial kernel to obtain single-exponential runtime in terms of vertex cover size, despite subset-minimization being not represented in the program’s structure. Then we turn our attention to strictly better structural parameters between vertex cover size and treewidth. Here, we provide double-exponential lower bounds for the most prominent parameters in that range: treedepth, feedback vertex size, and cliquewidth. Based on this, we argue that unfortunately our options beyond vertex cover size are limited. Our results provide an in-depth hardness study, relying on a novel reduction from normal to disjunctive programs, trading the increase of complexity for an exponential parameter compression.

PDF Details DOI

KR Conference 2023 Conference Paper

Knowledge Compilation and More with SharpSAT-TD

Rafael Kiesel
Thomas Eiter

SharpSAT-TD is a recently published exact model counter that performed exceptionally well in the recent editions of the Model Counting Competition (https: //mccompetition. org/). Notably, it additionally features *weighted* model counting capabilities over any semiring. In this work, we show how to exploit this fact to use SharpSAT-TD as a knowledge compiler to the class of sd-DNNF circuits. Our experimental evaluation shows that the efficiency of SharpSAT-TD for (weighted) model counting transfers to knowledge compilation, since it outperforms other state of the art knowledge compilers on standard benchmark sets. Additionally, we generalized SharpSAT-TD's preprocessing to support arbitrary semirings and consider the utility of auxiliary variables in this setting.

PDF Details DOI

JAIR Journal 2023 Journal Article

Semiring Reasoning Frameworks in AI and Their Computational Complexity

Thomas Eiter
Rafael Kiesel

Many important problems in AI, among them #SAT, parameter learning and probabilistic inference go beyond the classical satisfiability problem. Here, instead of finding a solution we are interested in a quantity associated with the set of solutions, such as the number of solutions, the optimal solution or the probability that a query holds in a solution. To model such quantitative problems in a uniform manner, a number of frameworks, e.g. Algebraic Model Counting and Semiring-based Constraint Satisfaction Problems, employ what we call the semiring paradigm. In the latter the abstract algebraic structure of the semiring serves as a means of parameterizing the problem definition, thus allowing for different modes of quantitative computations by choosing different semirings. While efficiently solvable cases have been widely studied, a systematic study of the computational complexity of such problems depending on the semiring parameter is missing. In this work, we characterize the latter by NP(R), a novel generalization of NP over semiring R, and obtain NP(R)-completeness results for a selection of semiring frameworks. To obtain more tangible insights into the hardness of NP(R), we link it to well-known complexity classes from the literature. Interestingly, we manage to connect the computational hardness to properties of the semiring. Using this insight, we see that, on the one hand, NP(R) is always at least as hard as NP or ModpP depending on the semiring R and in general unlikely to be in FPSPACEpoly. On the other hand, for broad subclasses of semirings relevant in practice we can employ reductions to NP, ModpP and #P. These results show that in many cases solutions are only mildly harder to compute than functions in NP, ModpP and #P, give us new insights into how problems that involve counting on semirings can be approached, and provide a means of assessing whether an algorithm is appropriate for a given class of problems.

PDF Details DOI

KR Conference 2023 Conference Paper

The Impact of Structure in Answer Set Counting: Fighting Cycles and its Limits

Markus Hecher
Rafael Kiesel

Answer Set Programming is a widely used paradigm in knowledge representation and reasoning, which strongly relates to the satisfiability (SAT) of propositional formulas. While in the area of SAT the last couple of years brought significant advances and different techniques for solving hard counting-based problems (e. g. , #SAT, weighted counting, projected counting) that require more effort than deciding satisfiability, ASP still falls short. Intuitively, one explanation for this lies in the structure of a program, that – compared to SAT – was shown to yield strong evidence for being slightly less useful during solving. Indeed, for the well-known structural measure treewidth that plays an important role in counting-based variants of SAT, ASP is expected to be at least slightly harder than SAT. The underlying source of this hardness increase lies in cyclic dependencies in the positive dependency graph. In this work, we consider which strategies are appropriate to tackle counting-based problems for ASP depending on cycle lengths. To this end, we present different encodings to counting-based variants of SAT that thereby directly utilize recent advances. For small cycle lengths, we demonstrate a novel strategy based on feedback vertex sets. While medium cycle lengths still leave room for future improvements, surprisingly, in case of cycles that are significantly larger than the structural dependencies (treewidth), we can even obtain a polynomial algorithm.

PDF Details DOI

AAAI Conference 2021 Conference Paper

On the Complexity of Sum-of-Products Problems over Semirings

Thomas Eiter
Rafael Kiesel

Many important problems in AI, among them SAT, #SAT, and probabilistic inference, amount to Sum-of-Products Problems, i. e. evaluating a sum of products of values from some semiring R. While efficiently solvable cases are known, a systematic study of the complexity of this problem is missing. We characterize the latter by NP(R), a novel generalization of NP over semiring R, and link it to well-known complexity classes. While NP(R) is unlikely to be contained in FPSPACE(POLY) in general, for a wide range of commutative (resp. in addition idempotent) semirings, there are reductions to #P (resp. NP) and solutions are thus only mildly harder to compute. We finally discuss NP(R)-complete reasoning problems in well-known semiring formalisms, among them Semiring-based Constraint Satisfaction Problems, obtaining new insights into their computational properties.

PDF Details

KR Conference 2021 Conference Paper

Treewidth-Aware Cycle Breaking for Algebraic Answer Set Counting

Thomas Eiter
Markus Hecher
Rafael Kiesel

Probabilistic reasoning, parameter learning, and most probable explanation inference for answer set programming have recently received growing attention. They are only some of the problems that can be formulated as Algebraic Answer Set Counting (AASC) problems. The latter are however hard to solve, and efficient evaluation techniques are needed. Inspired by Vlasser et al. 's Tp-compilation (JAR, 2016), we introduce Tp-unfolding, which employs forward reasoning to break the cycles in the positive dependency graph of a program by unfolding them. Tp-unfolding is defined for any normal answer set program and unfolds programs with respect to unfolding sequences, which are akin to elimination orders in SAT-solving. Using "good" unfolding sequences, we can ensure that the increase of the treewidth of the unfolded program is small. Treewidth is a measure adhering to a program's tree-likeness, which gives performance guarantees for AASC. We give sufficient conditions for the existence of good unfolding sequences based on the novel notion of component-boosted backdoor size, which measures the cyclicity of the positive dependencies in a program. The experimental evaluation of a prototype implementation, the AASC solver aspmc, shows promising results.

PDF Details DOI

ECAI Conference 2020 Conference Paper

Weighted LARS for Quantitative Stream Reasoning

Thomas Eiter
Rafael Kiesel

We extend LARS, which is a recent stream reasoning framework based on ASP, to weighted LARS (wLARS), where formulae are interpreted as algebraic expressions over semirings. This adds the ability to express quantitative measures of many different natures and to approach respective reasoning problems such as probabilistic reasoning, preferential reasoning and quantitative queries in a uniform manner. Notably, well-known quantitative ASP extensions can be formalized using wLARS, thus lifting them to the streaming setting. We identify a relevant wLARS fragment that is equivalent to weighted automata, which consequently gives us a rule-based language for expressing behaviors of such automata. Furthermore, we analyze evaluating wLARS formulae, showing that brave preferential reasoning is PSPACE- resp. Σ p 3 -complete in relevant settings.

Details