{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,2,20]],"date-time":"2024-02-20T09:59:15Z","timestamp":1708423155421},"reference-count":33,"publisher":"Oxford University Press (OUP)","issue":"8","license":[{"start":{"date-parts":[[2022,11,14]],"date-time":"2022-11-14T00:00:00Z","timestamp":1668384000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022,12,9]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>In this paper, we investigate the parameterized complexity of model checking for Dependence and Independence logic, which are well studied logics in the area of Team Semantics. We start with a list of nine immediate parameterizations for this problem, namely the number of disjunctions (i.e. splits)\/(free) variables\/universal quantifiers, formula-size, the tree-width of the Gaifman graph of the input structure, the size of the universe\/team and the arity of dependence atoms. We present a comprehensive picture of the parameterized complexity of model checking and obtain a division of the problem into tractable and various intractable degrees. Furthermore, we also consider the complexity of the most important variants (data and expression complexity) of the model checking problem by fixing parts of the input.<\/jats:p>","DOI":"10.1093\/logcom\/exac070","type":"journal-article","created":{"date-parts":[[2022,10,6]],"date-time":"2022-10-06T20:07:14Z","timestamp":1665086834000},"page":"1624-1644","source":"Crossref","is-referenced-by-count":2,"title":["A parameterized view on the complexity of dependence and independence logic"],"prefix":"10.1093","volume":"32","author":[{"given":"Juha","family":"Kontinen","sequence":"first","affiliation":[{"name":"Department of Mathematics and Statistics, University of Helsinki , PL 68, 00014 Helsinki, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arne","family":"Meier","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Theoretische Informatik , Leibniz Universit\u00e4t Hannover, 30167 Hannover, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yasir","family":"Mahmood","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Theoretische Informatik, Leibniz Universit\u00e4t Hannover , 30167 Hannover, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2022,11,14]]},"reference":[{"key":"2022121408225766300_ref1","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1137\/0608024","article-title":"Complexity of finding embeddings in a $k$-tree","volume":"2","author":"Arnborg","year":"1987","journal-title":"SIAM Journal on Algebraic Discrete Methods"},{"key":"2022121408225766300_ref2","first-page":"1","article-title":"A tourist guide through treewidth","volume":"11","author":"Bodlaender","year":"1993","journal-title":"Acta Cybernetica"},{"key":"2022121408225766300_ref3","first-page":"1","article-title":"Discovering treewidth","volume-title":"SOFSEM","author":"Bodlaender","year":"2005"},{"key":"2022121408225766300_ref4","article-title":"Texts in Computer Science","author":"Downey","year":"2013","journal-title":"Fundamentals of Parameterized Complexity"},{"key":"2022121408225766300_ref5","volume-title":"Fifty Years of the Spectrum Problem: Survey and New Results","author":"Durand","year":"2009"},{"key":"2022121408225766300_ref6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2362355.2362359","article-title":"Hierarchies in dependence logic","volume":"13","author":"Durand","year":"2012","journal-title":"ACM Transactions on Computational Logic (TOCL)"},{"key":"2022121408225766300_ref7","article-title":"Finite model theory","volume-title":"Perspectives in Mathematical Logic","author":"Ebbinghaus","year":"1995"},{"key":"2022121408225766300_ref8","doi-asserted-by":"crossref","first-page":"661","DOI":"10.1007\/s00453-014-9944-y","article-title":"On the space and circuit complexity of parameterized problems: classes and completeness","volume":"71","author":"Elberfeld","year":"2015","journal-title":"Algorithmica"},{"key":"2022121408225766300_ref9","article-title":"Texts in Theoretical Computer Science","volume-title":"Parameterized Complexity Theory","author":"Flum","year":"2006"},{"key":"2022121408225766300_ref10","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/j.apal.2011.08.005","article-title":"Inclusion and exclusion dependencies in team semantics\u2014on some logics of imperfect information","volume":"163","author":"Galliani","year":"2012","journal-title":"Annals of Pure and Applied Logic"},{"key":"2022121408225766300_ref11","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/j.apal.2011.08.005","article-title":"Inclusion and exclusion dependencies in team semantics: on some logics of imperfect information","volume":"163","author":"Galliani","year":"2012","journal-title":"Annals of Pure and Applied Logic"},{"key":"2022121408225766300_ref12","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1007\/978-3-319-31803-5_4","article-title":"On strongly first-order dependencies","volume-title":"Dependence Logic","author":"Galliani","year":"2016"},{"key":"2022121408225766300_ref13","first-page":"263","article-title":"Hierarchies in independence logic","volume-title":"Computer Science Logic 2013 (CSL 2013), CSL 2013, September 2\u20135, 2013, Torino, Italy","author":"Galliani","year":"2013"},{"key":"2022121408225766300_ref14","first-page":"281","article-title":"Inclusion logic and fixed point logic","volume-title":"Computer Science Logic 2013 (CSL 2013)","author":"Galliani","year":"2013"},{"key":"2022121408225766300_ref15","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/j.tcs.2012.10.033","article-title":"Model-checking games for logics of imperfect information","volume":"493","author":"Gr\u00e4del","year":"2013","journal-title":"Theoretical Computer Science"},{"key":"2022121408225766300_ref16","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1007\/s11225-013-9479-2","article-title":"Dependence and independence","volume":"101","author":"Gr\u00e4del","year":"2013","journal-title":"Studia Logica"},{"key":"2022121408225766300_ref17","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1007\/s11225-013-9479-2","article-title":"Dependence and independence","volume":"101","author":"Gr\u00e4del","year":"2013","journal-title":"Studia Logica"},{"key":"2022121408225766300_ref18","doi-asserted-by":"crossref","first-page":"879","DOI":"10.1093\/logcom\/exu057","article-title":"Hierarchies in independence and inclusion logic with strict semantics","volume":"25","author":"Hannula","year":"2015","journal-title":"Journal of Logic and Computation"},{"key":"2022121408225766300_ref19","doi-asserted-by":"crossref","first-page":"550","DOI":"10.1145\/3373718.3394773","article-title":"Descriptive complexity of real computation and probabilistic independence logic","volume-title":"LICS","author":"Hannula","year":"2020"},{"key":"2022121408225766300_ref20","doi-asserted-by":"crossref","first-page":"2:1","DOI":"10.1145\/3157054","article-title":"Complexity of propositional logics in team semantic","volume":"19","author":"Hannula","year":"2018","journal-title":"ACM Transactions on Computational Logic"},{"key":"2022121408225766300_ref21","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1007\/s11225-013-9481-8","article-title":"Coherence and computational complexity of quantifier-free dependence logic formulas","volume":"101","author":"Kontinen","year":"2013","journal-title":"Studia Logica"},{"key":"2022121408225766300_ref22","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-07003-1","article-title":"Texts in Theoretical Computer Science. An EATCS Series","author":"Libkin","year":"2004","journal-title":"Elements of Finite Model Theory"},{"key":"2022121408225766300_ref23","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1007\/s11225-013-9483-6","article-title":"Complexity results for modal dependence logic","volume":"101","author":"Lohmann","year":"2013","journal-title":"Studia Logica"},{"key":"2022121408225766300_ref24","article-title":"Canonical models and the complexity of modal team logic","volume":"15","author":"L\u00fcck","year":"2019","journal-title":"Logical Methods in Computer Science"},{"key":"2022121408225766300_ref25","first-page":"157","article-title":"Parameterised complexity of model checking and satisfiability in propositional dependence logic","volume-title":"Foundations of Information and Knowledge Systems\u201411th International Symposium, FoIKS 2020, Dortmund, Germany, February 17\u201321, 2020, Proceedings","author":"Mahmood","year":"2020"},{"key":"2022121408225766300_ref26","article-title":"Parameterised complexity of propositional logic in team semantics","author":"Mahmood","year":"2021"},{"key":"2022121408225766300_ref27","first-page":"417","article-title":"First-order model checking problems parameterized by the model","volume-title":"CiE","author":"Martin","year":"2008"},{"key":"2022121408225766300_ref28","first-page":"303","article-title":"Enumeration complexity of poor man\u2019s propositional dependence logic","volume-title":"FoIKS","author":"Meier","year":"2018"},{"key":"2022121408225766300_ref29","volume-title":"Computational Complexity","author":"Papadimitriou","year":"1994"},{"key":"2022121408225766300_ref30","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/0095-8956(84)90013-3","article-title":"Graph minors. III. planar tree-width","volume":"36","author":"Robertson","year":"1984","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"2022121408225766300_ref31","first-page":"425","article-title":"Fixed-parameter tractability","volume-title":"Handbook of Satisfiability","author":"Samer","year":"2009"},{"key":"2022121408225766300_ref32","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511611193","article-title":"London Mathematical Society Student Texts","volume-title":"Dependence Logic\u2014A New Approach to Independence Friendly Logic","author":"V\u00e4\u00e4n\u00e4nen","year":"2007"},{"key":"2022121408225766300_ref33","volume-title":"Approaches to Finite Variable Dependence: Expressiveness and Computational Complexity","author":"Virtema","year":"2014"}],"container-title":["Journal of Logic and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/logcom\/article-pdf\/32\/8\/1624\/47846347\/exac070.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/logcom\/article-pdf\/32\/8\/1624\/47846347\/exac070.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,14]],"date-time":"2022-12-14T11:43:49Z","timestamp":1671018229000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/logcom\/article\/32\/8\/1624\/6824421"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,14]]},"references-count":33,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2022,11,14]]},"published-print":{"date-parts":[[2022,12,9]]}},"URL":"https:\/\/doi.org\/10.1093\/logcom\/exac070","relation":{},"ISSN":["0955-792X","1465-363X"],"issn-type":[{"value":"0955-792X","type":"print"},{"value":"1465-363X","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2022,12]]},"published":{"date-parts":[[2022,11,14]]}}}