Details
| Original language | English |
|---|---|
| Title of host publication | SOFSEM 2025 |
| Subtitle of host publication | Theory and Practice of Computer Science - 50th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2025, Proceedings |
| Editors | Rastislav Královič, Věra Kůrková |
| Publisher | Springer Science and Business Media Deutschland GmbH |
| Pages | 31-44 |
| Number of pages | 14 |
| ISBN (electronic) | 978-3-031-82697-9 |
| ISBN (print) | 9783031826962 |
| Publication status | Published - 16 Feb 2025 |
| Event | 50th International Conference on Current Trends in Theory and Practice of Computer Science - Bratislava, Slovakia Duration: 20 Jan 2025 → 23 Jan 2025 |
Publication series
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volume | 15539 LNCS |
| ISSN (Print) | 0302-9743 |
| ISSN (electronic) | 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.
Keywords
- A-Hierarchy, Alternation, Model Checking, Parameterized Complexity Theory, SUBSET-SUM
ASJC Scopus subject areas
- Mathematics(all)
- Theoretical Computer Science
- Computer Science(all)
- General Computer Science
Cite this
- 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. ed. / Rastislav Královič; Věra Kůrková. Springer Science and Business Media Deutschland GmbH, 2025. p. 31-44 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 15539 LNCS).
Research output: Chapter in book/report/conference proceeding › Conference contribution › Research › 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 -