Details
| Originalsprache | Englisch |
|---|---|
| Titel des Sammelwerks | SOFSEM 2025 |
| Untertitel | Theory and Practice of Computer Science - 50th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2025, Proceedings |
| Herausgeber/-innen | Rastislav Královič, Věra Kůrková |
| Herausgeber (Verlag) | Springer Science and Business Media Deutschland GmbH |
| Seiten | 31-44 |
| Seitenumfang | 14 |
| ISBN (elektronisch) | 978-3-031-82697-9 |
| ISBN (Print) | 9783031826962 |
| Publikationsstatus | Veröffentlicht - 16 Feb. 2025 |
| Veranstaltung | 50th International Conference on Current Trends in Theory and Practice of Computer Science - Bratislava, Slowakei Dauer: 20 Jan. 2025 → 23 Jan. 2025 |
Publikationsreihe
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Band | 15539 LNCS |
| ISSN (Print) | 0302-9743 |
| ISSN (elektronisch) | 1611-3349 |
Abstract
The A-hierarchy is a parametric analogue of the polynomial hierarchy in the context of parameterised complexity theory. We give a new characterisation of the A-hierarchy in terms of a generalisation of the SUBSET-SUM problem.
ASJC Scopus Sachgebiete
- Mathematik (insg.)
- Theoretische Informatik
- Informatik (insg.)
- Allgemeine Computerwissenschaft
Zitieren
- Standard
- Harvard
- Apa
- Vancouver
- BibTex
- RIS
SOFSEM 2025: Theory and Practice of Computer Science - 50th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2025, Proceedings. Hrsg. / Rastislav Královič; Věra Kůrková. Springer Science and Business Media Deutschland GmbH, 2025. S. 31-44 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Band 15539 LNCS).
Publikation: Beitrag in Buch/Bericht/Sammelwerk/Konferenzband › Aufsatz in Konferenzband › Forschung › Peer-Review
}
TY - GEN
T1 - A SUBSET-SUM Characterisation of the A-Hierarchy
AU - Gutleben, Jan
AU - Meier, Arne
N1 - Publisher Copyright: © The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.
PY - 2025/2/16
Y1 - 2025/2/16
N2 - The A-hierarchy is a parametric analogue of the polynomial hierarchy in the context of parameterised complexity theory. We give a new characterisation of the A-hierarchy in terms of a generalisation of the SUBSET-SUM problem.
AB - The A-hierarchy is a parametric analogue of the polynomial hierarchy in the context of parameterised complexity theory. We give a new characterisation of the A-hierarchy in terms of a generalisation of the SUBSET-SUM problem.
KW - A-Hierarchy
KW - Alternation
KW - Model Checking
KW - Parameterized Complexity Theory
KW - SUBSET-SUM
UR - http://www.scopus.com/inward/record.url?scp=86000455755&partnerID=8YFLogxK
U2 - 10.1007/978-3-031-82697-9_3
DO - 10.1007/978-3-031-82697-9_3
M3 - Conference contribution
AN - SCOPUS:86000455755
SN - 9783031826962
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 31
EP - 44
BT - SOFSEM 2025
A2 - Královič, Rastislav
A2 - Kůrková, Věra
PB - Springer Science and Business Media Deutschland GmbH
T2 - 50th International Conference on Current Trends in Theory and Practice of Computer Science
Y2 - 20 January 2025 through 23 January 2025
ER -