Tractability Frontier of Data Complexity in Team Semantics
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 mo...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Open Publishing Association
2015-09-01
|
| Series: | Electronic Proceedings in Theoretical Computer Science |
| Online Access: | http://arxiv.org/pdf/1503.01144v2 |
| _version_ | 1818418604255739904 |
|---|---|
| author | Arnaud Durand Juha Kontinen Nicolas de Rugy-Altherre Jouko Väänänen |
| author_facet | Arnaud Durand Juha Kontinen Nicolas de Rugy-Altherre Jouko Väänänen |
| author_sort | Arnaud Durand |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-14T12:25:19Z |
| format | Article |
| id | doaj.art-ba033f5d90404de5bb697432fce2b8c9 |
| institution | Directory Open Access Journal |
| issn | 2075-2180 |
| language | English |
| last_indexed | 2024-12-14T12:25:19Z |
| publishDate | 2015-09-01 |
| publisher | Open Publishing Association |
| record_format | Article |
| series | Electronic Proceedings in Theoretical Computer Science |
| spelling | doaj.art-ba033f5d90404de5bb697432fce2b8c92022-12-21T23:01:21ZengOpen Publishing AssociationElectronic Proceedings in Theoretical Computer Science2075-21802015-09-01193Proc. GandALF 2015738510.4204/EPTCS.193.6:21Tractability Frontier of Data Complexity in Team SemanticsArnaud DurandJuha KontinenNicolas de Rugy-AltherreJouko VäänänenWe 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.http://arxiv.org/pdf/1503.01144v2 |
| spellingShingle | Arnaud Durand Juha Kontinen Nicolas de Rugy-Altherre Jouko Väänänen Tractability Frontier of Data Complexity in Team Semantics Electronic Proceedings in Theoretical Computer Science |
| title | Tractability Frontier of Data Complexity in Team Semantics |
| title_full | Tractability Frontier of Data Complexity in Team Semantics |
| title_fullStr | Tractability Frontier of Data Complexity in Team Semantics |
| title_full_unstemmed | Tractability Frontier of Data Complexity in Team Semantics |
| title_short | Tractability Frontier of Data Complexity in Team Semantics |
| title_sort | tractability frontier of data complexity in team semantics |
| url | http://arxiv.org/pdf/1503.01144v2 |
| work_keys_str_mv | AT arnauddurand tractabilityfrontierofdatacomplexityinteamsemantics AT juhakontinen tractabilityfrontierofdatacomplexityinteamsemantics AT nicolasderugyaltherre tractabilityfrontierofdatacomplexityinteamsemantics AT joukovaananen tractabilityfrontierofdatacomplexityinteamsemantics |