Details
| Original language | English |
|---|---|
| Pages (from-to) | 605-630 |
| Number of pages | 26 |
| Journal | Journal of logic and computation |
| Volume | 29 |
| Issue number | 5 |
| Early online date | 10 Apr 2019 |
| Publication status | Published - Sept 2019 |
Abstract
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.
Keywords
- complexity, Inclusion logic, model checking, team semantics, validity problem
ASJC Scopus subject areas
- Computer Science(all)
- Software
- Mathematics(all)
- Theoretical Computer Science
- Arts and Humanities(all)
- Arts and Humanities (miscellaneous)
- Computer Science(all)
- Hardware and Architecture
- Mathematics(all)
- Logic
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
In: Journal of logic and computation, Vol. 29, No. 5, 09.2019, p. 605-630.
Research output: Contribution to journal › Article › Research › peer review
}
TY - JOUR
T1 - Model checking and validity in propositional and modal inclusion logics
AU - Hella, Lauri
AU - Kuusisto, Antti
AU - Meier, Arne
AU - Virtema, Jonni
PY - 2019/9
Y1 - 2019/9
N2 - 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.
AB - 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.
KW - complexity
KW - Inclusion logic
KW - model checking
KW - team semantics
KW - validity problem
UR - http://www.scopus.com/inward/record.url?scp=85080893187&partnerID=8YFLogxK
U2 - 10.1093/logcom/exz008
DO - 10.1093/logcom/exz008
M3 - Article
AN - SCOPUS:85080893187
VL - 29
SP - 605
EP - 630
JO - Journal of logic and computation
JF - Journal of logic and computation
SN - 0955-792X
IS - 5
ER -