{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T16:51:16Z","timestamp":1773939076536,"version":"3.50.1"},"reference-count":43,"publisher":"Oxford University Press (OUP)","issue":"5","license":[{"start":{"date-parts":[[2019,4,11]],"date-time":"2019-04-11T00:00:00Z","timestamp":1554940800000},"content-version":"vor","delay-in-days":1,"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":[[2019,9,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Propositional and modal inclusion logic are formalisms that belong to the family of logics based on team semantics. This article investigates the model checking and validity problems of these logics. We identify complexity bounds for both problems, covering both lax and strict team semantics. By doing so, we come close to finalizing the programme that aims to completely classify the complexities of the basic reasoning problems for modal and propositional dependence, independence and inclusion logics.<\/jats:p>","DOI":"10.1093\/logcom\/exz008","type":"journal-article","created":{"date-parts":[[2019,3,19]],"date-time":"2019-03-19T21:12:18Z","timestamp":1553029938000},"page":"605-630","source":"Crossref","is-referenced-by-count":8,"title":["Model checking and validity in propositional and modal inclusion logics"],"prefix":"10.1093","volume":"29","author":[{"given":"Lauri","family":"Hella","sequence":"first","affiliation":[{"name":"Unit of Computing Sciences, Tampere University, Tampere, Finland"}]},{"given":"Antti","family":"Kuusisto","sequence":"additional","affiliation":[{"name":"Unit of Computing Sciences, Tampere University, Tampere, Finland"}]},{"given":"Arne","family":"Meier","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Theoretische Informatik, Leibniz Universit\u00e4t Hannover, Hanover, Germany"}]},{"given":"Jonni","family":"Virtema","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Statistics, University of Helsinki, Helsinki, Finland"},{"name":"Faculty of Sciences, Hasselt University, Hasselt, Belgium"}]}],"member":"286","published-online":{"date-parts":[[2019,4,10]]},"reference":[{"key":"2019091313044331400_ref1","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781107050884","volume-title":"Modal Logic","author":"Blackburn","year":"2001"},{"key":"2019091313044331400_ref2","first-page":"123","author":"Buss","year":"1987"},{"key":"2019091313044331400_ref3","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/0022-0000(84)90075-8","article-title":"Inclusion dependencies and their interaction with functional dependencies","volume":"28","author":"Casanova","year":"1984","journal-title":"Journal of Computer and Systems Sciences"},{"key":"2019091313044331400_ref4","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1145\/5397.5399","article-title":"Automatic verification of finite-state concurrent systems using temporal logic specifications","volume":"8","author":"Clarke","year":"1986","journal-title":"ACM ToPLS"},{"key":"2019091313044331400_ref5","first-page":"151","author":"Cook","year":"1971"},{"key":"2019091313044331400_ref6","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1007\/s10472-017-9568-4","article-title":"Approximation and dependence via multiteam semantics","volume":"83","author":"Durand","year":"2018","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"key":"2019091313044331400_ref7","first-page":"5","author":"Durand","year":"2016"},{"key":"2019091313044331400_ref8","first-page":"226","author":"Ebbing","year":"2012"},{"key":"2019091313044331400_ref9","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":"2019091313044331400_ref10","first-page":"281","author":"Galliani","year":"2013"},{"key":"2019091313044331400_ref11","volume-title":"Computers and Intractability, A Guide to the Theory of NP-Completeness","author":"Garey","year":"1979"},{"key":"2019091313044331400_ref12","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1145\/1008354.1008356","article-title":"The monotone and planar circuit value problems are log-space complete for P","volume":"9","author":"Goldschlager","year":"1977","journal-title":"SIGACT News"},{"key":"2019091313044331400_ref13","doi-asserted-by":"publisher","volume-title":"vol. 82 of Leibniz International Proceedings in Informatics (LIPIcs)","year":"2017","DOI":"10.4230\/LIPIcs.CSL.2017.28"},{"key":"2019091313044331400_ref14","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/j.ic.2016.04.001","article-title":"A finite axiomatization of conditional independence and inclusion dependencies","volume":"249","author":"Hannula","year":"2016","journal-title":"Information and Computation"},{"key":"2019091313044331400_ref15","first-page":"190","volume-title":"Deerfield Beach, FL, USA, January 8\u201311, 2018, Proceedings","author":"Hannula","year":"2018"},{"key":"2019091313044331400_ref16","doi-asserted-by":"publisher","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":"2019091313044331400_ref17","doi-asserted-by":"publisher","first-page":"32:1","DOI":"10.4230\/LIPIcs.MFCS.2017.32","article-title":"Model Checking and Validity in Propositional and Modal Inclusion Logics","author":"Hella","year":"2017"},{"key":"2019091313044331400_ref18","first-page":"281","article-title":"Modal inclusion logic: being lax is simpler than being strict","volume-title":"Proc. 40th MFCS","author":"Hella","year":"2015"},{"key":"2019091313044331400_ref19","author":"Hella","year":"2015"},{"key":"2019091313044331400_ref20","first-page":"129","author":"Hella","year":"2015"},{"key":"2019091313044331400_ref21","doi-asserted-by":"crossref","first-page":"539","DOI":"10.1093\/jigpal\/5.4.539","article-title":"Compositional semantics for a language of imperfect information","volume":"5","author":"Hodges","year":"1997","journal-title":"Logic Journal of the IGPL"},{"key":"2019091313044331400_ref22","first-page":"147","article-title":"Relational queries computable in polynomial time (extended abstract). In Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing","volume-title":"ACM","author":"Immerman","year":"1982"},{"key":"2019091313044331400_ref23","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1016\/j.jcss.2016.11.004","article-title":"Inclusion dependencies and their interaction with functional dependencies in SQL","volume":"85","author":"K\u00f6hler","year":"2017","journal-title":"Journal of Computer and Systems Sciences"},{"key":"2019091313044331400_ref24","first-page":"1333","article-title":"Modal independence logic","volume":"27","author":"Kontinen","year":"2017","journal-title":"Journal of Logic and Computation"},{"key":"2019091313044331400_ref25","doi-asserted-by":"publisher","first-page":"10:1","DOI":"10.4230\/LIPIcs.MFCS.2018.10","article-title":"Team Semantics for the Specification and Verification of Hyperproperties","volume-title":"43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), vol. 117 ofLeibniz International Proceedings in Informatics (LIPIcs)","author":"Krebs"},{"key":"2019091313044331400_ref26","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1137\/0206033","article-title":"The computational complexity of provability in systems of modal propositional logic","volume":"6","author":"Ladner","year":"1977","journal-title":"SIAM Journal on Computing"},{"key":"2019091313044331400_ref27","first-page":"265","article-title":"Universal sorting problems","volume":"9","author":"Levin","year":"1973","journal-title":"Problems of Information Transmission"},{"key":"2019091313044331400_ref28","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":"2019091313044331400_ref29","doi-asserted-by":"crossref","first-page":"928","DOI":"10.1016\/j.apal.2018.04.010","article-title":"Axiomatizations of team logics","volume":"169","author":"L\u00fcck","year":"2018","journal-title":"Annals of Pure and Applied Logic"},{"key":"2019091313044331400_ref30","author":"L\u00fcck"},{"key":"2019091313044331400_ref31","volume-title":"Satisfiability and Model Checking in Team Based Logics","author":"M\u00fcller","year":"2014"},{"key":"2019091313044331400_ref32","first-page":"957","author":"Peterson","year":"2001"},{"key":"2019091313044331400_ref33","author":"Sano"},{"key":"2019091313044331400_ref34","first-page":"140","article-title":"Characterizing frame definability in team semantics via the universal modality","volume":"2015","author":"Sano","year":"2015","journal-title":"In Proc. of WoLLIC"},{"key":"2019091313044331400_ref35","first-page":"392","article-title":"Characterizing relative frame definability in team semantics via the universal modality","volume":"2016","author":"Sano","year":"2016","journal-title":"In Proc. of WoLLIC"},{"key":"2019091313044331400_ref36","author":"Schnoebelen","year":"2002"},{"key":"2019091313044331400_ref37","doi-asserted-by":"crossref","first-page":"1157","DOI":"10.1093\/logcom\/exn102","article-title":"Model-theoretic and computational properties of modal dependence logic","volume":"19","author":"Sevenster","year":"2009","journal-title":"Journal of Logic and Computation"},{"key":"2019091313044331400_ref38","article-title":"Word problems requiring exponential time (preliminary report)","author":"Stockmeyer","year":"1973","journal-title":"Proc. 5th STOC"},{"key":"2019091313044331400_ref39","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511611193","volume-title":"Dependence Logic","author":"V\u00e4\u00e4n\u00e4nen","year":"2007"},{"key":"2019091313044331400_ref40","first-page":"137","article-title":"The complexity of relational query languages (extended abstract). In Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing","author":"Vardi","year":"1982"},{"key":"2019091313044331400_ref41","first-page":"253224","article-title":"Complexity of validity for propositional dependence logics","author":"Virtema","year":"2017","journal-title":"Information and Computation"},{"key":"2019091313044331400_ref42","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03927-4","volume-title":"Introduction to Circuit Complexity\u2014A Uniform Approach","author":"Vollmer","year":"1999"},{"key":"2019091313044331400_ref43","doi-asserted-by":"crossref","first-page":"1406","DOI":"10.1016\/j.apal.2017.01.007","article-title":"Propositional team logics","volume":"168","author":"Yang","year":"2017","journal-title":"Annals of Pure and Applied Logic"}],"container-title":["Journal of Logic and Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/logcom\/article-pdf\/29\/5\/605\/30010720\/exz008.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,13]],"date-time":"2019-09-13T17:09:14Z","timestamp":1568394554000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/logcom\/article\/29\/5\/605\/5427467"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4,10]]},"references-count":43,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2019,4,10]]},"published-print":{"date-parts":[[2019,9,12]]}},"URL":"https:\/\/doi.org\/10.1093\/logcom\/exz008","relation":{},"ISSN":["0955-792X","1465-363X"],"issn-type":[{"value":"0955-792X","type":"print"},{"value":"1465-363X","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2019,9]]},"published":{"date-parts":[[2019,4,10]]}}}