  We study the characterization and computation of general policies for
families of problems that share a structure characterized by a common reduction
into a single abstract problem. Policies $\mu$ that solve the abstract problem
P have been shown to solve all problems Q that reduce to P provided that $\mu$
terminates in Q. In this work, we shed light on why this termination condition
is needed and how it can be removed. The key observation is that the abstract
problem P captures the common structure among the concrete problems Q that is
local (Markovian) but misses common structure that is global. We show how such
global structure can be captured by means of trajectory constraints that in
many cases can be expressed as LTL formulas, thus reducing generalized planning
to LTL synthesis. Moreover, for a broad class of problems that involve integer
variables that can be increased or decreased, trajectory constraints can be
compiled away, reducing generalized planning to fully observable
non-deterministic planning.
