## On the decidability of reachability in linear time-invariant
systems

*Nathanaël Fijalkow*,
*Joël
Ouaknine*, *Amaury Pouly*, *João Sousa Pinto*, and *James Worrell*
We consider the decidability of state-to-state reachability in linear
time-invariant control systems over discrete time. We analyse this
problem with respect to the allowable control sets, which in general
we assume to be given by boolean combinations of linear inequalities.
Decidability of the version of the reachability problem in which
control sets are affine subspaces of **R**^{n}
is a fundamental result in
control theory. Our first result is that reachability is undecidable if
the set of controls is a finite union of affine subspaces. We also
consider versions of the reachability problem in which (i) the set of
controls consists of a single affine subspace together with the origin
and (ii) the set of controls is a convex polytope. In these two cases
we respectively show that the reachability problem is as hard as
Skolem's Problem and the Positivity Problem for linear recurrence
sequences (whose decidability has been open for several decades). Our
main contribution is to show decidability of a version of the
reachability problem in which control sets are convex polytopes, under
certain spectral assumptions on the transition matrix.

*Proceedings of HSCC 19*, 2019. 10 pages.

PDF
© 2019 ACM.

Imprint / Data Protection