| Autor: |
Arnaud Durand, Juha Kontinen, Nicolas de Rugy-Altherre, Jouko Väänänen |
| Jazyk: |
angličtina |
| Rok vydání: |
2015 |
| Předmět: |
|
| Zdroj: |
Electronic Proceedings in Theoretical Computer Science, Vol 193, Iss Proc. GandALF 2015, Pp 73-85 (2015) |
| Druh dokumentu: |
article |
| ISSN: |
2075-2180 |
| DOI: |
10.4204/EPTCS.193.6 |
| Popis: |
We study the data complexity of model-checking for logics with team semantics. For dependence and independence logic, we completely characterize the tractability/intractability frontier of data complexity of both quantifier-free and quantified formulas. For inclusion logic formulas, we reduce the model-checking problem to the satisfiability problem of so-called Dual-Horn propositional formulas. Via this reduction, we give an alternative proof for the recent result showing that the data complexity of inclusion logic is in PTIME. |
| Databáze: |
Directory of Open Access Journals |
| Externí odkaz: |
|
