Complexity Results in Team Semantics: Nonemptiness Is Not So Complex
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917524150419456 |
|---|---|
| author | Anttila, Aleksi Kontinen, Juha Yang, Fan |
| author_facet | Anttila, Aleksi Kontinen, Juha Yang, Fan |
| contents | We initiate the study of the complexity-theoretic properties of convex logics in team semantics. We focus on the extension of classical propositional logic with the nonemptiness atom NE, a logic known to be both convex and union closed. We show that the satisfiability problem for this logic is NP-complete, that its validity problem is coNP-complete, and that its model-checking problem is in P. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_08122 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Complexity Results in Team Semantics: Nonemptiness Is Not So Complex Anttila, Aleksi Kontinen, Juha Yang, Fan Logic in Computer Science Logic 03D15, 03B60 F.2.2; F.4.1 We initiate the study of the complexity-theoretic properties of convex logics in team semantics. We focus on the extension of classical propositional logic with the nonemptiness atom NE, a logic known to be both convex and union closed. We show that the satisfiability problem for this logic is NP-complete, that its validity problem is coNP-complete, and that its model-checking problem is in P. |
| title | Complexity Results in Team Semantics: Nonemptiness Is Not So Complex |
| topic | Logic in Computer Science Logic 03D15, 03B60 F.2.2; F.4.1 |
| url | https://arxiv.org/abs/2510.08122 |