| Identifikační kód | RIV/00216224:14330/15:00087406 |
|---|
| Název v anglickém jazyce | A complete parameterized complexity analysis of bounded planning |
|---|
| Druh | J - Článek v odborném periodiku |
|---|
| Jazyk | eng - angličtina |
|---|
| Obor - skupina | I - Informatika |
|---|
| Obor | IN - Informatika |
|---|
| Rok uplatnění | 2015 |
|---|
| Kód důvěrnosti údajů | S - Úplné a pravdivé údaje o výsledku nepodléhající ochraně podle zvláštních právních předpisů. |
|---|
| Počet výskytů výsledku | 1 |
|---|
| Počet tvůrců celkem | 4 |
|---|
| Počet domácích tvůrců | 1 |
|---|
| Výčet všech uvedených jednotlivých tvůrců | Christer Backstrom (státní příslušnost: SE - Švédské království)
Peter Jonsson (státní příslušnost: SE - Švédské království)
Sebastian Ordyniak (státní příslušnost: DE - Spolková republika Německo, domácí tvůrce: A)
Stefan Szeider (státní příslušnost: AT - Rakouská republika) |
|---|
| Popis výsledku v anglickém jazyce | The propositional planning problem is a notoriously difficult computational problem, which remains hard even under strong syntactical and structural restrictions. Given its difficulty it becomes natural to study planning in the context of parameterized complexity. In this paper we continue the work initiated by Downey, Fellows and Stege on the parameterized complexity of planning with respect to the parameter "length of the solution plan." We provide a complete classification of the parameterized complexity of the planning problem under two of the most prominent syntactical restrictions, i.e., the so called PUBS restrictions introduced by Backstrom and Nebel and restrictions on the number of preconditions and effects as introduced by Bylander. We alsodetermine which of the considered fixed-parameter tractable problems admit a polynomial kernel and which do not. |
|---|
| Klíčová slova oddělená středníkem | Complexity of automated planning; Parameterized complexity; Kernelization |
|---|
| Stránka www, na které se nachází výsledek | - |
|---|
| DOI výsledku | 10.1016/j.jcss.2015.04.002 |
|---|