Author name cluster

Stefan Rümmele

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.

7 papers

2 author rows

AAAI Conference 2018 Conference Paper

Minesweeper with Limited Moves

Serge Gaspers
Stefan Rümmele
Abdallah Saffidine
Kevin Tran

We consider the problem of playing Minesweeper with a limited number of moves: Given a partially revealed board, a number of available clicks k, and a target probability p, can we win with probability p. We win if we do not click on a mine, and, after our sequence of at most k clicks (which reveal information about the neighboring squares) can correctly identify the placement of all mines. We make the assumption, that, at all times, all placements of mines consistent with the currently revealed squares are equiprobable. Our main results are that the problem is PSPACE-complete, and it remains PSPACE-complete when p is a constant, in particular when p = 1. When k = 0 (i. e. , we are not allowed to click anywhere), the problem is PP-complete in general, but co-NP-complete when p is a constant, and in particular when p = 1.

PDF Details

ECAI Conference 2014 Conference Paper

Belief merging within fragments of propositional logic

Nadia Creignou
Odile Papini
Stefan Rümmele
Stefan Woltran

Recently, belief change within the framework of fragments of propositional logic has gained increasing attention. Previous works focused on belief contraction and belief revision on the Horn fragment. However, the problem of belief merging within fragments of propositional logic has been neglected so far. This paper presents a general approach to define new merging operators derived from existing ones such that the result of merging remains in the fragment under consideration. Our approach is not limited to the case of Horn fragment but applicable to any fragment of propositional logic characterized by a closure property on the sets of models of its formulæ . We study the logical properties of the proposed operators in terms of satisfaction of merging postulates, considering in particular distance-based merging operators for Horn and Krom fragments.

Details

IJCAI Conference 2013 Conference Paper

Backdoors to Abduction

Andreas Pfandler
Stefan Rümmele
Stefan Szeider

Abductive reasoning (or Abduction, for short) is among the most fundamental AI reasoning methods, with a broad range of applications, including fault diagnosis, belief revision, and automated planning. Unfortunately, Abduction is of high computational complexity; even propositional Abduction is ΣP 2-complete and thus harder than NP and co-NP. This complexity barrier rules out the existence of a polynomial transformation to propositional satisfiability (SAT). In this work we use structural properties of the Abduction instance to break this complexity barrier. We utilize the problem structure in terms of small backdoor sets. We present fixedparameter tractable transformations from Abduction to SAT, which make the power of today’s SAT solvers available to Abduction.

PDF Details DOI

AAAI Conference 2012 Conference Paper

The Parameterized Complexity of Abduction

Michael Fellows
Andreas Pfandler
Frances Rosamond
Stefan Rümmele

Abduction belongs to the most fundamental reasoning methods. It is a method for reverse inference, this means one is interested in explaining observed behavior by finding appropriate causes. We study logic-based abduction, where knowledge is represented by propositional formulas. The computational complexity of this problem is highly intractable in many interesting settings. In this work we therefore present an extensive parameterized complexity analysis of abduction within various fragments of propositional logic together with (combinations of) natural parameters.

PDF Details

JELIA Conference 2010 Conference Paper

A Dynamic-Programming Based ASP-Solver

Michael Morak
Reinhard Pichler
Stefan Rümmele
Stefan Woltran

Abstract We present a novel system for propositional Answer-Set Programming (ASP). This system, called dynASP, is based on dynamic programming and thus significantly differs from standard ASP-solvers which implement techniques stemming from SAT or CSP.

Details

KR Conference 2010 Conference Paper

Tractable Answer-Set Programming with Weight Constraints: Bounded Treewidth is not Enough

Reinhard Pichler
Stefan Rümmele
Stefan Szeider
Stefan Woltran

Cardinality constraints or, more generally, weight constraints are well recognized as an important extension of answer-set programming. Clearly, all common algorithmic tasks related to programs with cardinality or weight constraints (PWCs) – like checking the consistency of a program – are intractable. Many intractable problems in the area of knowledge representation and reasoning have been shown to become tractable if the treewidth of the programs or formulas under consideration is bounded by some constant. The goal of this paper is to apply the notion of treewidth to PWCs and to identify tractable fragments. It will turn out that the straightforward application of treewidth to PWCs does not suﬃce to obtain tractability. However, by imposing further restrictions, tractability can be achieved. Main results of the paper • We show that the consistency problem of PWCs remains NP-complete even if the treewidth of the considered programs is bounded by a constant (actually, even if this constant is 1). Hence, we have to search for further restrictions on the PWCs to ensure tractability. • We thus consider the largest integer occurring in (lower and upper) bounds of the constraints in the PWC, and call this parameter constraint-width. If also the constraint-width is bounded by an arbitrary but ﬁxed constant, then the consistency problem of PWCs becomes linear time tractable (the bound on the running time entails a constant factor that is exponential in constraint-width and treewidth). • For PCCs (i. e., PWCs where all weights are equal to 1) we obtain non-uniform polynomial time tractability by designing a new dynamic programming algorithm, i. e.: Let w denote the treewidth of a PCC and let n denote the size of the PCC. Then our algorithm works in time O(f (w) · n2w) for some function f that only depends on the treewidth, but not on the size n of the program. The term “non-uniform” refers to the factor n2w in the time bound, where the size n of the program is raised to the power of an expression that depends on the treewidth w. We shall also discuss further extensions of this dynamic programming algorithm for PCCs, e. g.: it can be used to solve in non-uniform polynomial time the consistency problem of PWCs if the weights are given in unary representation. • Of course, an algorithm for the PCC consistency problem that operates in time O(f (w) · nO(1)) would be preferable, i. e., the parameter w does not occur in the exponent

LPAR Conference 2008 Conference Paper

Fast Counting with Bounded Treewidth

Michael Jakl
Reinhard Pichler
Stefan Rümmele
Stefan Woltran

Abstract Many intractable problems have been shown to become tractable if the treewidth of the underlying structure is bounded by a constant. An important tool for deriving such results is Courcelle’s Theorem, which states that all properties defined by Monadic-Second Order (MSO) sentences are fixed-parameter tractable with respect to the treewidth. Arnborg et al. extended this result to counting problems defined via MSO properties. However, the MSO description of a problem is of course not an algorithm. Consequently, proving the fixed-parameter tractability of some problem via Courcelle’s Theorem can be considered as the starting point rather than the endpoint of the search for an efficient algorithm. Gottlob et al. have recently presented a new approach via monadic datalog to actually devise efficient algorithms for decision problems whose tractability follows from Courcelle’s Theorem. In this paper, we extend this approach and apply it to some fundamental counting problems in logic an artificial intelligence.

Details