@article{45849,
  abstract     = {{<jats:title>Abstract</jats:title><jats:p>Dependence Logic was introduced by Jouko Väänänen in 2007. We study a propositional variant of this logic<jats:italic>(PDL)</jats:italic>and investigate a variety of parameterisations with respect to central decision problems. The model checking problem (MC) of<jats:italic>PDL</jats:italic>is<jats:bold>NP</jats:bold>-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 be<jats:bold>NP</jats:bold>-complete as well (Lohmann and Vollmer, Studia Logica 2013). There we are presenting a different picture: under team-size, or dep-arity SAT is<jats:bold>paraNP</jats:bold>-complete whereas under all other mentioned parameters the problem is<jats:bold>FPT</jats:bold>. 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.</jats:p>}},
  author       = {{Mahmood, Yasir and Meier, Arne}},
  issn         = {{1012-2443}},
  journal      = {{Annals of Mathematics and Artificial Intelligence}},
  keywords     = {{Applied Mathematics, Artificial Intelligence}},
  number       = {{2-3}},
  pages        = {{271--296}},
  publisher    = {{Springer Science and Business Media LLC}},
  title        = {{{Parameterised complexity of model checking and satisfiability in propositional dependence logic}}},
  doi          = {{10.1007/s10472-021-09730-w}},
  volume       = {{90}},
  year         = {{2022}},
}

@article{3037,
  abstract     = {{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.}},
  author       = {{Alt, Helmut and Behrends, Bernd and Blömer, Johannes}},
  issn         = {{1573-7470}},
  journal      = {{Annals of Mathematics and Artificial Intelligence}},
  number       = {{3}},
  title        = {{{Approximate matching of polygonal shapes}}},
  volume       = {{13}},
  year         = {{1995}},
}