> Merkliste Sie können Bookmarks mittels Listen verwalten, loggen Sie sich dafür bitte in Ihr SLUB Benutzerkonto ein.
Medientyp: E-Artikel; Sonstige Veröffentlichung Titel: Parameterised complexity of model checking and satisfiability in propositional dependence logic Beteiligte: Mahmood, Yasir [VerfasserIn]; Meier, Arne [VerfasserIn] Erschienen: Dordrecht [u.a.] : Springer Science + Business Media B.V, 2021 Erschienen in: Annals of mathematics and artificial intelligence 90 (2022), Nr. 2-3 ; Annals of mathematics and artificial intelligence Ausgabe: published Version Sprache: Englisch DOI: https://doi.org/10.15488/12823; https://doi.org/10.1007/s10472-021-09730-w Schlagwörter: Model checking ; Propositional dependence logic ; Parameterised complexity ; Satisfiability Entstehung: Anmerkungen: Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen. Beschreibung: Dependence 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) of PDL is NP-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 NP-complete as well (Lohmann and Vollmer, Studia Logica 2013). There we are presenting a different picture: under team-size, or dep-arity SAT is paraNP-complete whereas under all other mentioned parameters the problem is FPT. 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. © 2021, The Author(s). Zugangsstatus: Freier Zugang Rechte-/Nutzungshinweise: Namensnennung (CC BY)