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 -