In this paper, we present the Generalized State-Variable formalism. The GSV is a strongly structured representation of states and actions in planning, where states are characterized by finite domain state-variables, and actions modify a set of state-variable values. The use of variables is allowed in the description of plan operators. In this representation, we established two new solution criteria. The first one consists in a global condition to be verified by the set of state-variables in the plan, and lead to the definition of a new efficient planning algorithm. The second is more like the SNLP criterion. With these two criteria the notions of instantiated state-variables, and semi-instantiated plans are introduced. We Show that these two criteria are equivalent, and are necessary and sufficient conditions in the semi-instantiated plan restriction. We also argue for the relevance of both of these criteria. Finally, we discuss generality and interests of this new formalization of planning problems, and we relate it to the classical STRIPS representation.