Sökning: WFRF:(Bäckström Sebastian) >
A complete paramete...
A complete parameterized complexity analysis of bounded planning
-
- Bäckström, Christer (författare)
- Linköpings universitet,Programvara och system,Tekniska fakulteten
-
- Jonsson, Peter (författare)
- Linköpings universitet,Programvara och system,Tekniska fakulteten
-
- Ordyniak, Sebastian (författare)
- Masaryk University, Czech Republic
-
visa fler...
-
- Szeider, Stefan (författare)
- Vienna University of Technology, Austria
-
visa färre...
-
(creator_code:org_t)
- Elsevier, 2015
- 2015
- Engelska.
-
Ingår i: Journal of computer and system sciences (Print). - : Elsevier. - 0022-0000 .- 1090-2724. ; 81:7, s. 1311-1332
- Relaterad länk:
-
https://doi.org/10.1...
-
visa fler...
-
https://urn.kb.se/re...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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 also determine which of the considered fixed-parameter tractable problems admit a polynomial kernel and which do not. (C) 2015 Elsevier Inc. All rights reserved.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences (hsv//eng)
Nyckelord
- Complexity of automated planning; Parameterized complexity; Kernelization
Publikations- och innehållstyp
- ref (ämneskategori)
- art (ämneskategori)
Hitta via bibliotek
Till lärosätets databas