  We prove that every flat nonlinear discrete-time system can be decomposed by
coordinate transformations into a smaller-dimensional subsystem and an
endogenous dynamic feedback. For flat continuous-time systems, no comparable
result is available. The advantage of such a decomposition is that the complete
system is flat if and only if the subsystem is flat. Thus, by repeating the
decomposition at most $n-1$ times, where $n$ is the dimension of the state
space, the flatness of a discrete-time system can be checked in an algorithmic
way. If the system is flat, then the algorithm yields a flat output which only
depends on the state variables. Hence, every flat discrete-time system has a
flat output which does not depend on the inputs and their forward-shifts.
Again, no comparable result for flat continuous-time systems is available. The
algorithm requires in each decomposition step the construction of state- and
input transformations, which are obtained by straightening out certain vector
fields or distributions with the flow-box theorem or the Frobenius theorem.
Thus, from a computational point of view, only the calculation of flows and the
solution of algebraic equations is needed. We illustrate our results by two
examples.
