Abstract We give a formal de?nition of generalized planning that is independent of any representation formalism. We assume that our generalized plans must work on a set of deterministic environments, which are essentially unrelated to each other. We prove that generalized planning for a ?nite set of environments is always decidable and EXPSPACEcomplete. Our proof is constructive and gives us a sound, complete and complexity-wise optimal technique. We also consider in?nite sets of environments, and show that generalized planning for the in?nite “one-dimensional problems,” known in the literature to be recursively enumerable when restricted to ?nite-state plans, is EXPSPACE-decidable without sequence functions, and solvable by generalized planning for ?nite sets.