  The paper introduces a novel representation for Generalized Planning (GP)
problems, and their solutions, as C++ programs. Our C++ representation allows
to formally proving the termination of generalized plans, and to specifying
their asymptotic complexity w.r.t. the number of world objects. Characterizing
the complexity of C++ generalized plans enables the application of a
combinatorial search that enumerates the space of possible GP solutions in
order of complexity. Experimental results show that our implementation of this
approach, which we call BFGP++, outperforms the previous GP as heuristic search
approach for the computation of generalized plans represented as
compiler-styled programs. Last but not least, the execution of a C++ program on
a classical planning instance is a deterministic grounding-free and search-free
process, so our C++ representation allows us to automatically validate the
computed solutions on large test instances of thousands of objects, where
off-the-shelf classical planners get stuck either in the pre-processing or in
the search.
