TY - JOUR
AB - AbstractDependence Logic was introduced by Jouko Väänänen in 2007. We study a propositional variant of this logic(PDL)and investigate a variety of parameterisations with respect to central decision problems. The model checking problem (MC) ofPDLisNP-complete (Ebbing and Lohmann, SOFSEM 2012). The subject of this research is to identify a list of parameterisations (formula-size, formula-depth, treewidth, team-size, number of variables) under which MC becomes fixed-parameter tractable. Furthermore, we show that the number of disjunctions or the arity of dependence atoms (dep-arity) as a parameter both yield a paraNP-completeness result. Then, we consider the satisfiability problem (SAT) which classically is known to beNP-complete as well (Lohmann and Vollmer, Studia Logica 2013). There we are presenting a different picture: under team-size, or dep-arity SAT isparaNP-complete whereas under all other mentioned parameters the problem isFPT. Finally, we introduce a variant of the satisfiability problem, asking for a team of a given size, and show for this problem an almost complete picture.
AU - Mahmood, Yasir
AU - Meier, Arne
ID - 45849
IS - 2-3
JF - Annals of Mathematics and Artificial Intelligence
KW - Applied Mathematics
KW - Artificial Intelligence
SN - 1012-2443
TI - Parameterised complexity of model checking and satisfiability in propositional dependence logic
VL - 90
ER -
TY - JOUR
AB - For two given simple polygonsP, Q, the problem is to determine a rigid motionI ofQ giving the best possible match betweenP andQ, i.e. minimizing the Hausdorff distance betweenP andI(Q). Faster algorithms as the one for the general problem are obtained for special cases, namely thatI is restricted to translations or even to translations only in one specified direction. It turns out that determining pseudo-optimal solutions, i.e. ones that differ from the optimum by just a constant factor, can be done much more efficiently than determining optimal solutions. In the most general case, the algorithm for the pseudo-optimal solution is based on the surprising fact that for the optimal possible match betweenP and an imageI(Q) ofQ, the distance between the centroids of the edges of the convex hulls ofP andI(Q) is a constant multiple of the Hausdorff distance betweenP andI(Q). It is also shown that the Hausdorff distance between two polygons can be determined in timeO(n logn), wheren is the total number of vertices.
AU - Alt, Helmut
AU - Behrends, Bernd
AU - Blömer, Johannes
ID - 3037
IS - 3
JF - Annals of Mathematics and Artificial Intelligence
SN - 1573-7470
TI - Approximate matching of polygonal shapes
VL - 13
ER -