A complete parameterized complexity analysis of bounded planning

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F15%3A00087406" target="_blank" >RIV/00216224:14330/15:00087406 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1016/j.jcss.2015.04.002" target="_blank" >http://dx.doi.org/10.1016/j.jcss.2015.04.002</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.jcss.2015.04.002" target="_blank" >10.1016/j.jcss.2015.04.002</a>

Jazyk výsledku

angličtina

Název v původním jazyce

A complete parameterized complexity analysis of bounded planning

Popis výsledku v původní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.

Název v anglickém jazyce

A complete parameterized complexity analysis of bounded planning

Popis výsledku anglicky

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.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/EE2.3.30.0009" target="_blank" >EE2.3.30.0009: Zaměstnáním čerstvých absolventů doktorského studia k vědecké excelenci</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2015

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Journal of Computer and System Sciences

ISSN

0022-0000

e-ISSN

—

Svazek periodika

81

Číslo periodika v rámci svazku

7

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

22

Strana od-do

1311-1332

Kód UT WoS článku

000356644600014

EID výsledku v databázi Scopus

—