Conference item
Karp's NP-complete problems over first-order definable structures
- Abstract:
- We determine the decidability of Karp’s NP-complete problems on structures which are first-order definable over the theory of equality, also known as orbit-finite sets with atoms or nominal sets.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Accepted manuscript, pdf, 529.2KB, Terms of use)
-
- Publisher copy:
- 10.1007/978-3-032-22730-0_15
Authors
- Publisher:
- Springer
- Host title:
- Foundations of Software Science and Computation Structures: 29th International Conference, FoSSaCS 2026, Held as Part of the International Joint Conferences on Theory and Practice of Software, ETAPS 2026, Turin, Italy, April 11–16, 2026, Proceedings
- Pages:
- 307-327
- Series:
- Lecture Notes in Computer Science
- Series number:
- 16503
- Publication date:
- 2026-04-15
- Acceptance date:
- 2025-12-22
- Event title:
- 29th International Conference on Foundations of Software Science and Computation Structures (FoSSaCS 2026)
- Event location:
- Turin, Italy
- Event website:
- https://etaps.org/2026/conferences/fossacs/
- Event start date:
- 2026-04-11
- Event end date:
- 2026-04-16
- DOI:
- EISSN:
-
1611-3349
- ISSN:
-
0302-9743
- EISBN:
- 9783032227300
- ISBN:
- 9783032227294
- Language:
-
English
- Keywords:
- Pubs id:
-
2364937
- Local pid:
-
pubs:2364937
- Deposit date:
-
2026-01-29
- ARK identifier:
Terms of use
- Copyright holder:
- Healy and Klin
- Copyright date:
- 2026
- Rights statement:
- © The Editor(s) (if applicable) and The Author(s), under exclusive license to Springer Nature Switzerland AG 2026.
- Notes:
- This paper will be presented at the 29th International Conference on Foundations of Software Science and Computation Structures (FoSSaCS 2026), 11th-16th April 2026, Turn, Italy. The author accepted manuscript (AAM) of this paper has been made available under the University of Oxford's Open Access Publications Policy, and a CC BY public copyright licence has been applied.
- Licence:
- CC Attribution (CC BY)
If you are the owner of this record, you can report an update to it here: Report update to this record