dc.identifier.uri |
http://dx.doi.org/10.15488/12823 |
|
dc.identifier.uri |
https://www.repo.uni-hannover.de/handle/123456789/12926 |
|
dc.contributor.author |
Mahmood, Yasir
|
|
dc.contributor.author |
Meier, Arne
|
|
dc.date.accessioned |
2022-09-30T05:19:38Z |
|
dc.date.available |
2022-09-30T05:19:38Z |
|
dc.date.issued |
2021 |
|
dc.identifier.citation |
Mahmood, Y.; Meier, A.: Parameterised complexity of model checking and satisfiability in propositional dependence logic. In: Annals of mathematics and artificial intelligence 90 (2022), Nr. 2-3, S. 271-296. DOI: https://doi.org/10.1007/s10472-021-09730-w |
|
dc.description.abstract |
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). |
eng |
dc.language.iso |
eng |
|
dc.publisher |
Dordrecht [u.a.] : Springer Science + Business Media B.V |
|
dc.relation.ispartofseries |
Annals of mathematics and artificial intelligence 90 (2022), Nr. 2-3 |
|
dc.rights |
CC BY 4.0 Unported |
|
dc.rights.uri |
https://creativecommons.org/licenses/by/4.0/ |
|
dc.subject |
Model checking |
eng |
dc.subject |
Parameterised complexity |
eng |
dc.subject |
Propositional dependence logic |
eng |
dc.subject |
Satisfiability |
eng |
dc.subject.ddc |
510 | Mathematik
|
ger |
dc.subject.ddc |
004 | Informatik
|
ger |
dc.title |
Parameterised complexity of model checking and satisfiability in propositional dependence logic |
eng |
dc.type |
Article |
|
dc.type |
Text |
|
dc.relation.essn |
1573-7470 |
|
dc.relation.doi |
https://doi.org/10.1007/s10472-021-09730-w |
|
dc.bibliographicCitation.issue |
2-3 |
|
dc.bibliographicCitation.volume |
90 |
|
dc.bibliographicCitation.date |
2022 |
|
dc.bibliographicCitation.firstPage |
271 |
|
dc.bibliographicCitation.lastPage |
296 |
|
dc.description.version |
publishedVersion |
|
tib.accessRights |
frei zug�nglich |
|