  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 Baeckstroem 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 don't.
