---
_id: '45849'
abstract:
- lang: eng
  text: '<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:
- first_name: Yasir
  full_name: Mahmood, Yasir
  id: '99353'
  last_name: Mahmood
- first_name: Arne
  full_name: Meier, Arne
  last_name: Meier
citation:
  ama: Mahmood Y, Meier A. Parameterised complexity of model checking and satisfiability
    in propositional dependence logic. <i>Annals of Mathematics and Artificial Intelligence</i>.
    2022;90(2-3):271-296. doi:<a href="https://doi.org/10.1007/s10472-021-09730-w">10.1007/s10472-021-09730-w</a>
  apa: Mahmood, Y., &#38; Meier, A. (2022). Parameterised complexity of model checking
    and satisfiability in propositional dependence logic. <i>Annals of Mathematics
    and Artificial Intelligence</i>, <i>90</i>(2–3), 271–296. <a href="https://doi.org/10.1007/s10472-021-09730-w">https://doi.org/10.1007/s10472-021-09730-w</a>
  bibtex: '@article{Mahmood_Meier_2022, title={Parameterised complexity of model checking
    and satisfiability in propositional dependence logic}, volume={90}, DOI={<a href="https://doi.org/10.1007/s10472-021-09730-w">10.1007/s10472-021-09730-w</a>},
    number={2–3}, journal={Annals of Mathematics and Artificial Intelligence}, publisher={Springer
    Science and Business Media LLC}, author={Mahmood, Yasir and Meier, Arne}, year={2022},
    pages={271–296} }'
  chicago: 'Mahmood, Yasir, and Arne Meier. “Parameterised Complexity of Model Checking
    and Satisfiability in Propositional Dependence Logic.” <i>Annals of Mathematics
    and Artificial Intelligence</i> 90, no. 2–3 (2022): 271–96. <a href="https://doi.org/10.1007/s10472-021-09730-w">https://doi.org/10.1007/s10472-021-09730-w</a>.'
  ieee: 'Y. Mahmood and A. Meier, “Parameterised complexity of model checking and
    satisfiability in propositional dependence logic,” <i>Annals of Mathematics and
    Artificial Intelligence</i>, vol. 90, no. 2–3, pp. 271–296, 2022, doi: <a href="https://doi.org/10.1007/s10472-021-09730-w">10.1007/s10472-021-09730-w</a>.'
  mla: Mahmood, Yasir, and Arne Meier. “Parameterised Complexity of Model Checking
    and Satisfiability in Propositional Dependence Logic.” <i>Annals of Mathematics
    and Artificial Intelligence</i>, vol. 90, no. 2–3, Springer Science and Business
    Media LLC, 2022, pp. 271–96, doi:<a href="https://doi.org/10.1007/s10472-021-09730-w">10.1007/s10472-021-09730-w</a>.
  short: Y. Mahmood, A. Meier, Annals of Mathematics and Artificial Intelligence 90
    (2022) 271–296.
date_created: 2023-07-03T11:45:39Z
date_updated: 2024-06-04T16:06:59Z
doi: 10.1007/s10472-021-09730-w
extern: '1'
intvolume: '        90'
issue: 2-3
keyword:
- Applied Mathematics
- Artificial Intelligence
language:
- iso: eng
page: 271-296
publication: Annals of Mathematics and Artificial Intelligence
publication_identifier:
  issn:
  - 1012-2443
  - 1573-7470
publication_status: published
publisher: Springer Science and Business Media LLC
status: public
title: Parameterised complexity of model checking and satisfiability in propositional
  dependence logic
type: journal_article
user_id: '99353'
volume: 90
year: '2022'
...
---
_id: '3037'
abstract:
- lang: eng
  text: 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:
- first_name: Helmut
  full_name: Alt, Helmut
  last_name: Alt
- first_name: Bernd
  full_name: Behrends, Bernd
  last_name: Behrends
- first_name: Johannes
  full_name: Blömer, Johannes
  id: '23'
  last_name: Blömer
citation:
  ama: Alt H, Behrends B, Blömer J. Approximate matching of polygonal shapes. <i>Annals
    of Mathematics and Artificial Intelligence</i>. 1995;13(3).
  apa: Alt, H., Behrends, B., &#38; Blömer, J. (1995). Approximate matching of polygonal
    shapes. <i>Annals of Mathematics and Artificial Intelligence</i>, <i>13</i>(3).
  bibtex: '@article{Alt_Behrends_Blömer_1995, title={Approximate matching of polygonal
    shapes}, volume={13}, number={3}, journal={Annals of Mathematics and Artificial
    Intelligence}, author={Alt, Helmut and Behrends, Bernd and Blömer, Johannes},
    year={1995} }'
  chicago: Alt, Helmut, Bernd Behrends, and Johannes Blömer. “Approximate Matching
    of Polygonal Shapes.” <i>Annals of Mathematics and Artificial Intelligence</i>
    13, no. 3 (1995).
  ieee: H. Alt, B. Behrends, and J. Blömer, “Approximate matching of polygonal shapes,”
    <i>Annals of Mathematics and Artificial Intelligence</i>, vol. 13, no. 3, 1995.
  mla: Alt, Helmut, et al. “Approximate Matching of Polygonal Shapes.” <i>Annals of
    Mathematics and Artificial Intelligence</i>, vol. 13, no. 3, 1995.
  short: H. Alt, B. Behrends, J. Blömer, Annals of Mathematics and Artificial Intelligence
    13 (1995).
date_created: 2018-06-05T08:38:41Z
date_updated: 2022-01-06T06:58:53Z
department:
- _id: '64'
extern: '1'
intvolume: '        13'
issue: '3'
language:
- iso: eng
publication: Annals of Mathematics and Artificial Intelligence
publication_identifier:
  issn:
  - 1573-7470
publication_status: published
quality_controlled: '1'
status: public
title: Approximate matching of polygonal shapes
type: journal_article
user_id: '25078'
volume: 13
year: '1995'
...