Department of Computer Science, University of Oxford,
UKjulianrdcosta@gmail.comhttps://orcid.org/0000-0003-2610-5241emmy.network
foundation under the aegis of the Fondation de Luxembourg. Max Planck
Institute for Software Systems, Saarland Informatics Campus, Germanytoghs@mpi-
sws.orghttps://orcid.org/0000-0002-9405-2332 Max Planck Institute for Software
Systems, Kaiserslautern, Germanyrupak@mpi-
sws.orghttps://orcid.org/0000-0003-2136-0542DFG grant 389792660 as part of TRR
248 (see https://perspicuous-computing.science). Max Planck Institute for
Software Systems, Saarland Informatics Campus, Germanyjoel@mpi-
sws.orghttps://orcid.org/0000-0003-0031-9356DFG grant 389792660 as part of TRR
248 (see https://perspicuous-computing.science). Joël Ouaknine is also
affiliated with Keble College, Oxford as emmy.network Fellow. Max Planck
Institute for Software Systems, Kaiserslautern, Germanymsalamati@mpi-
sws.orghttps://orcid.org/0000-0003-3790-3935 Department of Computer Science,
University of Oxford, UKjbw@cs.ox.ac.ukhttps://orcid.org/0000-0001-8151-2443
J. D’Costa, T. Karimov, R. Majumdar, J. Ouaknine, M. Salamati, S. Soudjani and
J. Worrell [100]Theory of computation → Logic → Logic and verification
https://arxiv.org/abs/2204.12253 Stefan Szeider, Robert Ganian, and Alexandra
Silva 3 47th International Symposium on Mathematical Foundations of Computer
Science (MFCS 2022) MFCS 2022 MFCS 2022 August 22–26, 2022 Vienna, Austria 241
75

# The Pseudo-Reachability Problem for Diagonalisable Linear Dynamical Systems

Julian D’Costa  Toghrul Karimov  Rupak Majumdar  Joël Ouaknine  Mahmoud
Salamati  James Worrell

###### Abstract

We study fundamental reachability problems on pseudo-orbits of linear
dynamical systems. Pseudo-orbits can be viewed as a model of computation with
limited precision and pseudo-reachability can be thought of as a robust
version of classical reachability. Using an approach based on $o$-minimality
of $\mathbb{R}_{\exp}$ we prove decidability of the discrete-time pseudo-
reachability problem with arbitrary semialgebraic targets for diagonalisable
linear dynamical systems. We also show that our method can be used to reduce
the continuous-time pseudo-reachability problem to the (classical) time-
bounded reachability problem, which is known to be conditionally decidable.

###### keywords:

pseudo-orbits, Orbit problem, Skolem problem, linear dynamical systems,
reachability

###### category:

##  1 Introduction

A _discrete-time linear dynamical system_ (LDS) is given by an update matrix
$M\in\mathbb{Q}^{d\times d}$ and a starting point $s\in\mathbb{Q}^{d}$. An LDS
describes a system whose state contains $d$ rational numbers and evolves
linearly. The _orbit_ of such a system is the infinite sequence $\langle
s,Ms,M^{2}s,\ldots\rangle$ of points in $\mathbb{Q}^{d}$. Orbits of LDS arise
in many areas of computer science and mathematics, including verification of
linear loops [10], automata theory [3], and the theory of linear recurrence
sequences [17].

A fundamental problem about LDS is the question of deciding, given a system
$\langle M,s\rangle$ and a semialgebraic target set
$S\subseteq\mathbb{R}^{d}$, whether there exists $n$ such that $M^{n}s\in S$.
This problem is known as the _reachability problem for LDS_ and has been
studied extensively over the last few decades. In their seminal work, Kannan
and Lipton showed that the point-to-point reachability problem, i.e., the case
in which $S$ is a singleton, is decidable in polynomial time. At the same time
they observed that the case in which $S$ is a $(d-1)$-dimensional subspace of
$\mathbb{R}^{d}$ (i.e. a hyperplane) is equivalent to the famous _Skolem
problem_ whose decidability remains open to this day. The Skolem problem asks,
given a linear recurrence sequence defined by a recurrence relation
$u_{n+d}=a_{1}u_{n}+\ldots+a_{d}u_{n+d-1}$ and initial values
$u_{0},\ldots,u_{d-1}$, to decide whether there exists $n$ such that
$u_{n}=0$. In addition to this Skolem-hardness, the difficulty of settling the
reachability problem was further demonstrated by the results of [16], which
show that solving the reachability problem with halfspace targets, known as
the _positivity problem_ , would entail major mathematical breakthroughs in
the field of Diophantine approximation.

The reachability problem is defined with reference to the exact dynamics of an
LDS. Since computational systems typically operate with finite precision, it
is natural to consider an alternate notion of reachability involving so-called
_pseudo-orbits_. The notion of pseudo-orbit is an important conceptual tool in
dynamical systems that was introduced by Anosov [2], Bowen [4], and Conley
[6], and was used by the latter to prove what is sometimes called the
fundamental theorem of dynamical systems. Given an LDS $\langle M,s\rangle$, a
sequence $\langle x_{n}\mid n\in\mathbb{N}\rangle$ is an _$\epsilon$ -pseudo-
orbit_ of $s$ under $M$ if $x_{0}=s$ and $\|Mx_{n}-x_{n+1}\|<\epsilon$ for all
$n\in\mathbb{N}$. In other words, in a pseudo-orbit one considers an enlarged
transition relation that is obtained by considering the dynamical system up to
precision $\epsilon$. Given $\epsilon>0$, a set $S$ is said to be _$\epsilon$
-pseudo-reachable_ if there exists an $\epsilon$-pseudo-orbit $\langle
x_{0}=s,x_{1},x_{2},\ldots\rangle$ of $s$ under $M$ that reaches $S$. We
further say that $S$ is _pseudo-reachable_ if $S$ is $\epsilon$-pseudo-
reachable for every $\epsilon>0$. If a set $S$ of error states is not pseudo-
reachable then we can consider the system as being safe if implemented with
sufficient precision, while if $S$ is pseudo-reachable, it means that no
finite amount of precision suffices to make the system reliably safe.

Recently, D’Costa et al. [7] considered the pseudo-reachability problem and,
somewhat surprisingly, showed decidability in cases where $S$ is a point (the
pseudo-orbit problem), a hyperplane (the pseudo-Skolem problem) or a halfspace
(the pseudo-positivity problem). Their proof of the first result relies on an
exact characterisation of $\epsilon$-pseudo-orbits. Their solution to the
latter two problems, however, depends heavily on the fact that a hyperplane (a
halfspace) can be defined using a single equality (inequality), an approach
which unfortunately cannot be generalised to arbitrary semialgebraic targets.
In this work, we develop a novel logical approach to show the decidability of
the pseudo-reachability problem for diagonalisable systems with arbitrary
semialgebraic targets.

###  1.1 High-level proof sketch of our approach

Our solution to the diagonalisable pseudo-reachability problem can be
summarised as follows. Let ${\widetilde{\mathcal{O}}}_{\epsilon}(n)$ denote
the set of all points that are reachable exactly at time $n$ via an
$\epsilon$-pseudo-orbit. The pseudo-reachability problem then consists in
checking whether the sentence $\Phi\coloneqq\forall\epsilon.\,\exists
n\in\mathbb{N}:{\widetilde{\mathcal{O}}}_{\epsilon}(n)\cap S\neq\emptyset$ is
true. In this form, $\Phi$ is not amenable to application of logical methods
as it involves both integer and real-valued variables, in addition to
exponentiation with a complex base (coming from non-real eigenvalues of $M$).
We therefore first move to the continuous domain and construct an abstraction
$\mathcal{A}_{\epsilon}(t)$ for $t\in\mathbb{R}^{\geq 0}$ that is definable in
${\mathbb{R}_{\exp}}$ such that
$\mathcal{A}_{\epsilon}(n)\supseteq{\widetilde{\mathcal{O}}}_{\epsilon}(n)$
for all $n\in\mathbb{N}$. We then investigate the values of $\epsilon$ and $t$
that make $\Psi(\epsilon,t)\coloneqq\mathcal{A}_{\epsilon}(t)\cap
S\neq\emptyset$ true. We show that by the $o$-minimality of
${\mathbb{R}_{\exp}}$, either for every $\epsilon>0$ there exists $T$ such
that for all $t>T$, $\Psi(\epsilon,t)$ holds, or the pseudo-reachability
problem is equivalent to a finite-horizon reachability problem that is easily
solvable. In the former case, it follows that for every $\epsilon>0$,
$\Psi(\epsilon,n)$ holds for all sufficiently large integer values $n$, thus
establishing a bridge back to the discrete setting. We conclude by showing
that in this case, $S$ is pseudo-reachable. Intuitively, the idea is to use
the universal quantification over $\epsilon$ to argue that if $S$ can be
reached using an $\epsilon/2$-abstraction at all but finitely many time steps,
then it can be reached by an $\epsilon$-pseudo-orbit, in fact at infinitely
many possible time steps. The importance of the universal quantification is
also illustrated by the following hardness result. For any fixed $\epsilon>0$,
it is decidable whether $\exists
n\in\mathbb{N}:\,\mathcal{A}_{\epsilon}(n)\cap S\neq\emptyset$ holds, whereas
the $\epsilon$-pseudo-reachability problem of determining whether $\exists
n\in\mathbb{N}:\,{\widetilde{\mathcal{O}}}_{\epsilon}(n)\cap S\neq\emptyset$
holds is hard with respect to (a hard subclass of) the Skolem problem, as
shown in section 4.

The approach outlined above can be adapted to solve a few other related
problems about linear dynamical systems. An example would be the _robust
reachability problem_ recently considered by Akshay et al. in [1]: given an
LDS $\langle M,s\rangle$ and a semialgebraic target $S$, decide whether for
all $\epsilon>0$ there exists a point $s^{\prime}$ in the
$\epsilon$-neighbourhood of $s$ whose orbit reaches $S$. This problem can be
thought of as a modification of the pseudo-reachability problem where only one
perturbation is allowed at the very beginning. Due to this simplification, we
are able to show, in Appendix A, full decidability (that is, without the
restriction to diagonalisable systems) of the robust reachability problem.
Finally, because the first step of our solution is to translate the problem
into the continuous domain, the continuous versions of both the pseudo-
reachability problem (discussed in section 5) and the robust reachability
problem (discussed in Appendix B) can be handled using the same approach,
arguably more naturally. For the former, because we proceed by reducing the
pseudo-reachability problem to bounded-time reachability problem, the
decidability result assumes Schanuel’s conjecture.

##  2 Mathematical tools

We write $B(c,r)$ for the closed $\ell_{2}$-ball of radius $r$ centred around
$c\in\mathbb{R}^{d}$ and ${\mathbf{0}}\in\mathbb{R}^{d}$ for the
$d$-dimensional zero vector. We denote by $\mathbb{T}\subseteq\mathbb{C}$ the
unit circle in the complex plane and by $||x||$ the $\ell_{2}$-norm of a
vector $x\in\mathbb{R}^{d}$.

###  2.1 First-order logic

We denote by $\mathbb{R}_{0}$ the (structure of) real numbers with addition
and multiplication, by ${\mathbb{R}_{\exp}}$ the real numbers with addition,
multiplication and (unbounded) exponentiation and by
$\mathbb{R}_{\exp,\cos{\upharpoonright}[0,T]}$ the real numbers with
exponentiation and bounded (in input, by some $T>0$) trigonometric functions.
By the Tarski-Seidenberg theorem, the theory of $\mathbb{R}_{0}$ admits
effective quantifier elimination and is therefore decidable. The theories of
${\mathbb{R}_{\exp}}$ and $\mathbb{R}_{\exp,\cos{\upharpoonright}[0,T]}$ are
known to be decidable subject to Schanuel’s conjecture (see, e.g., [11]) in
transcendental number theory [13, 19]. However
$\mathbb{R}_{\exp,\cos{\upharpoonright}[0,T]}$ (and hence
${\mathbb{R}_{\exp}}$ and $\mathbb{R}_{0}$) are unconditionally known to be
$o$-minimal [18]. That is, any subset of $\mathbb{R}$ definable using
arithmetic operations, real exponentiation and bounded trigonometric functions
is a finite union of intervals. In particular, any subset of $\mathbb{R}^{\geq
0}$ definable in this way is either bounded or contains all sufficiently large
real numbers. For the discrete-time problems considered in this paper we will
only need to work with ${\mathbb{R}_{\exp}}$. We will need
$\mathbb{R}_{\exp,\cos{\upharpoonright}[0,T]}$ only when considering the
classical bounded-time reachability problem for continuous-time linear
dynamical systems.

A _semialgebraic_ set is a subset of $\mathbb{R}^{d}$ definable (without
parameters) in $\mathbb{R}_{0}$. We say that a function
$\varphi:\mathbb{R}^{l}\to\mathbb{R}^{m}$ is semialgebraic if its graph is a
semialgebraic subset of $\mathbb{R}^{l+m}$. Intuitively, semialgebraic
functions are exactly the functions that can be specified using arithmetic and
logical operations over the real numbers.

###  2.2 Kronecker’s theorem and its applications

The analysis of problems about linear dynamical systems often reduces to that
of the orbit $\langle\Gamma^{n}\mid n\in\mathbb{N}\rangle$ where
$\Gamma^{n}=(\gamma_{1}^{n},\ldots,\gamma_{k}^{n})$ for
$\gamma_{1},\ldots,\gamma_{k}\in\mathbb{T}$. Let
$\mathcal{T}=\operatorname{cl}(\\{\Gamma^{n}:n\in\mathbb{N}\\})$ be the
topological closure of this discrete orbit. The set $\mathcal{T}$ is
semialgebraic and well-understood with the help of Kronecker’s theorem in
simultaneous Diophantine approximation [9].

######  Theorem 2.1 (Kronecker).

Let $\theta_{1},\ldots,\theta_{k},\varphi_{1},\ldots,\varphi_{k}\in\mathbb{R}$
be such that for any $a_{1},\ldots,a_{k}\in\mathbb{Z}$,

$\sum_{i=1}^{k}a_{i}\theta_{i}\in\mathbb{Z}\Rightarrow\sum_{i=1}^{k}a_{i}\varphi_{i}\in\mathbb{Z}.$

For any $\epsilon>0$ there exist infinitely many $n\in\mathbb{N}$ such that
$\\{n\theta_{i}-\varphi_{i}\\}<\epsilon$ for all $1\leq i\leq k$, where
$\\{x\\}$ denotes the distance from $x\in\mathbb{R}$ to the nearest integer.

To apply this theorem to our situation, let

$\mathcal{T}=\\{(z_{1},\ldots,z_{k}):\forall
a_{1},\ldots,a_{k}\in\mathbb{Z}:\,\gamma_{1}^{a_{1}}\cdots\gamma_{k}^{a_{k}}=1\Rightarrow
z_{1}^{a_{1}}\cdots z_{k}^{a_{k}}=1\\}.$

For $z=(z_{1},\ldots,z_{k})\in\mathcal{T}$, by considering
$\theta_{i}=\frac{\operatorname{arg}(\gamma_{i})}{2\pi}$ and
$\varphi_{i}=\frac{\operatorname{arg}(z_{i})}{2\pi}$ for $1\leq i\leq k$ we
can deduce that for each $\epsilon>0$ there exists $n$ such that
$||z-\Gamma^{n}||<\epsilon$ and hence the orbit $\langle\Gamma^{n}\mid
n\in\mathbb{N}\rangle$ is dense in $\mathcal{T}$. On the other hand, using
Masser’s deep results [14] about multiplicative relations between algebraic
numbers one can compute, in polynomial time, a finite basis for
$\\{(a_{1},\ldots,a_{k})\in\mathbb{Z}^{k}:\gamma_{1}^{a_{1}}\cdots\gamma_{k}^{a_{k}}=1\\}$.
Hence $\mathcal{T}$ is closed, semialgebraic and effectively computable. It
then follows that
$\mathcal{T}=\operatorname{cl}(\\{\Gamma^{n}:n\in\mathbb{N}\\})$.

We will also need the following lemma which is a consequence of the effective
computability of
$\mathcal{T}=\operatorname{cl}(\\{\Gamma^{n}:n\in\mathbb{N}\\})$ as a
semialgebraic set.

######  Lemma 2.2.

Let
$R=\operatorname{diag}(\Lambda_{1},\ldots,\Lambda_{k})\in\mathbb{R}^{2k\times
2k}$ be a block diagonal matrix where $\Lambda_{i}$ is an algebraic rotation
matrix for $1\leq i\leq k$. The closure of the set
$\\{R^{n}x:n\in\mathbb{N}\\}$, for $x$ with algebraic entries, is
semialgebraic and effectively computable.

The proof follows immediately from diagonalising $R^{n}$ and observing that
all eigenvalues of $R$ are algebraic numbers in $\mathbb{T}$.

##  3 Decidability for discrete-time diagonalisable systems

In this section we prove our main result: the decidability of the pseudo-
reachability problem for discrete-time diagonalisable _affine dynamical
systems_ , which are a generalisation of LDS.
The reason we consider affine systems is that the well-known homogenisation
trick (increasing the dimension by one and adding a coordinate that is always
equal to $1$) used for reducing the classical reachability problem for affine
systems to the reachability problem for LDS doesn’t work for the pseudo-
reachability problem: when perturbations are allowed, one cannot force a
coordinate to remain constant. Hence affine systems require separate
treatment.

######  Problem 3.1 (pseudo-reachability).

Let $M\in\mathbb{Q}^{L\times L}$ be an update matrix, $s\in\mathbb{Q}^{L}$ be
a starting point, $b\in\mathbb{Q}^{L}$ be an affine term and
$S\subseteq\mathbb{R}^{L}$ be a semialgebraic target set. A sequence $\langle
x_{0}=s,x_{1},x_{2}\ldots\rangle$ is an _$\epsilon$_ -pseudo-orbit of $s$ if
$||Mx_{n}+b-x_{n+1}||\leq\epsilon$ for all $n$. The pseudo-reachability
problem asks: given $M,b,s$ and $S$, decide whether for each $\epsilon>0$
there exists an $\epsilon$-pseudo-orbit of $s$ that reaches the set $S$.

Let ${\widetilde{\mathcal{O}}}_{\epsilon}(n)$ denote the set of all points
that are reachable via an $\epsilon$-pseudo-orbit of $s$ under the map
$x\mapsto Mx+b$ at time $n$. Since
${\widetilde{\mathcal{O}}}_{\epsilon}(0)=\\{s\\}$ and
${\widetilde{\mathcal{O}}}_{\epsilon}(n+1)=M{\widetilde{\mathcal{O}}}_{\epsilon}(n)+b+\epsilon
B({\mathbf{0}},1)$, by induction we can show that
${\widetilde{\mathcal{O}}}_{\epsilon}(n)=M^{n}s+\sum_{i=0}^{n-1}M^{i}b+\epsilon\sum_{i=0}^{n-1}M^{i}B({\mathbf{0}},1)$.
The pseudo-reachability problem is then equivalent to determining the truth of
$\forall\epsilon.\,\exists n:{\widetilde{\mathcal{O}}}_{\epsilon}(n)\cap
S\neq\emptyset$. Here $B({\mathbf{0}},1)$ can be viewed as a set of “control
inputs”, and the pseudo-reachability problem can be viewed as the problem of
determining whether $S$ can be reached using arbitrarily small control inputs.
The next lemma shows that we can in fact, choose any reasonable control set.

######  Lemma 3.2 (Invariance under change of the control set).

Let $\mathcal{B}\subseteq\mathbb{R}^{L}$ be a bounded set containing an open
ball around the origin.

  1. 1.

The pseudo-reachability problem as defined above is equivalent to the problem
of determining whether

$\forall\epsilon.\,\exists
n:(M^{n}s+\sum_{i=0}^{n-1}M^{i}b+\epsilon\sum_{i=0}^{n-1}M^{i}\mathcal{B})\cap
S\neq\emptyset.$

  2. 2.

We may assume the matrix $M$ is in real Jordan form.

######  Proof 3.3.

Since $\mathcal{B}$ is assumed to be bounded and to contain an open
neighbourhood around the origin, there must exist constants $C_{1},C_{2}$ such
that $C_{1}B({\mathbf{0}},1)\subseteq\mathcal{B}\subseteq
C_{2}B({\mathbf{0}},1)$. Hence

$C_{1}\epsilon\sum_{i=0}^{n-1}M^{i}B({\mathbf{0}},1)\subseteq\epsilon\sum_{i=0}^{n-1}M^{i}\mathcal{B}\subseteq
C_{2}\epsilon\sum_{i=0}^{n-1}M^{i}B({\mathbf{0}},1).$

The proof of (1) then follows from the fact that $\epsilon$ is universally
quantified: one can simulate (i) an $\epsilon$-pseudo-orbit with control set
$\mathcal{B}$ using a $C_{2}\epsilon$-pseudo-orbit with control set
$B({\mathbf{0}},1)$ and (ii) an $\epsilon$-pseudo-orbit with control set
$B({\mathbf{0}},1)$ using a $\epsilon/C_{1}$-pseudo-orbit with control set
$\mathcal{B}$. Proof of (2) follows from observing that multiplying
$B({\mathbf{0}},1)$ by an invertible change of basis matrix results in a
bounded control set containing a neighbourhood around ${\mathbf{0}}$.

Observe that the change of the control set described above is not applicable
when $\epsilon$ is fixed, as in the $\epsilon$-pseudo-reachability problem
discussed in section 4.

###  3.1 A closed form for ${\widetilde{\mathcal{O}}}_{\epsilon}(n)$

We now use 3.2 to choose a control set that results in
${\widetilde{\mathcal{O}}}_{\epsilon}(n)$ with a convenient first-order closed
form: observe that the naïve formulation above involves the term
$\sum_{i=0}^{n-1}M^{i}B({\mathbf{0}},1)$ which is not “first-order”.

Assume $M$ is diagonalisable and in real Jordan form:
$M=\operatorname{diag}(\Lambda_{1},\ldots,\Lambda_{k},\rho_{k+1},\ldots,\rho_{d})$.
That is, $M$ consists of $d$ block, the first $k$ of which have dimension
$2\times 2$ and a pair of non-real conjugate eigenvalues, whereas the
remaining blocks are $1\times 1$ and real. Write $\rho_{j}$ for the spectral
radius of the $j$th block. We can factor $M$ into a “scaling” and a “rotation”
as $M=DR$ where
$D=\operatorname{diag}(\rho_{1},\rho_{1},\ldots,\rho_{k},\rho_{k},\rho_{k+1},\rho_{k+2},\ldots,\rho_{d})$
is diagonal and $R$ is a block-diagonal matrix that consists of blocks that
are either $2\times 2$ rotation matrices or $1\times 1$ and equal to
$\begin{bmatrix}\pm 1\end{bmatrix}$. Hereafter we will be using the convenient
“rotation-invariant” control set

$\mathcal{B}=\prod_{j=1}^{k}B((0,0),1)\times\prod_{j=k+1}^{d}[-1,1]=\prod_{j=1}^{d}B({\mathbf{0}},1)$

where $B((0,0),1)$ is the unit disc. Observe that $\mathcal{B}$ is a product
of $\ell_{2}$-balls that matches the block structure of $M$. It follows that
$R\mathcal{B}=\mathcal{B}$ and hence

${\widetilde{\mathcal{O}}}_{\epsilon}(n)=D^{n}R^{n}s+\sum_{i=0}^{n-1}M^{i}b+\epsilon\sum_{i=0}^{n-1}D^{i}R^{i}\mathcal{B}=D^{n}R^{n}s+\sum_{i=0}^{n-1}M^{i}b+\epsilon\mathcal{B}(n)$

where $\mathcal{B}(n)=\sum_{i=0}^{n-1}D^{i}\mathcal{B}$. We then have

$\mathcal{B}(n)=\sum_{i=0}^{n-1}D^{i}\prod_{j=1}^{d}B({\mathbf{0}},1)=\sum_{i=0}^{n-1}\prod_{j=1}^{d}B({\mathbf{0}},\rho_{j}^{i})=\prod_{j=0}^{d}B({\mathbf{0}},\sum_{i=0}^{n-1}\rho_{j}^{i}).$

Geometrically, the idea is that a $2\times 2$ or a $1\times 1$ block of $D$
maps an origin-centred disc (which corresponds to a symmetric interval in 1D)
to an origin-centred disc, and a set-sum of such discs is again an origin-
centred disc. Note that our ability to reason in this way crucially depends on
the fact that $M$ is diagonalisable. Finally, since
$\sum_{i=0}^{n-1}\rho_{j}^{i}$ is either $\frac{\rho_{j}^{n}-1}{\rho_{j}-1}$
or $n\rho_{j}$, we can write
$\mathcal{B}(n)=\\{z:\varphi(z,n,\rho_{1}^{n},\ldots,\rho_{d}^{n})\\}$, where
$\varphi$ is a semialgebraic predicate.

We can apply the blockwise summation technique, distinguishing between the
cases where the spectral radius of the block is 1 or different from 1, to the
term $\sum_{i=0}^{n-1}M^{i}b$ to obtain the closed form
$\sum_{i=0}^{n-1}M^{i}b=D^{n}R^{n}x^{\prime}+cn+d$, where $x^{\prime}$, $c$
and $d$ only depend on $M$ and $b$. We then fold $s$ and $x^{\prime}$ into a
new, fictive starting point $x$ to obtain the final closed form

${\widetilde{\mathcal{O}}}_{\epsilon}(n)=D^{n}R^{n}x+cn+d+\epsilon\mathcal{B}(n).$

In order to solve the pseudo-reachability problem, we henceforth consider the
problem of determining the truth of the sentence $\forall\epsilon>0.\,\exists
n:(D^{n}R^{n}x+cn+d+\epsilon\mathcal{B}(n))\cap S\neq 0$, where all the input
vectors and matrices have real algebraic entries.

###  3.2 Passing to the abstraction

The expression for ${\widetilde{\mathcal{O}}}_{\epsilon}(n)$ contains the term
$D^{n}R^{n}x$, which is the last obstacle to obtaining an expression which we
can attack using known results about theories of real numbers. To address this
issue we resort to abstracting ${\widetilde{\mathcal{O}}}_{\epsilon}(n)$. Let

$\mathcal{T}:=\operatorname{cl}\left(\\{R^{n}x:n\in\mathbb{N}\\}\right)\textrm{
and }\mathcal{A}_{\epsilon}(n):=D^{n}\mathcal{T}+cn+d+\epsilon\mathcal{B}(n)$

where $\mathcal{T}$ is the closure of the orbit of $x$ under $R$, and is
semialgebraic and effectively computable by the discussion in subsection 2.2.
Moreover, recall that by Kronecker’s theorem for every $z\in\mathcal{T}$ and
$\epsilon>0$ there exist infinitely many integers $0<n_{1}<n_{2}<\ldots$ such
that $||R^{n_{i}}x-z||<\epsilon$ for all $i$.

Here $\mathcal{A}_{\epsilon}(n)$ acts as an abstraction of
${\widetilde{\mathcal{O}}}_{\epsilon}(n)$. In particular, for all $\epsilon>0$
and $n\in\mathbb{N}$ we have
$\mathcal{A}_{\epsilon}(n)\supseteq{\widetilde{\mathcal{O}}}_{\epsilon}(n)$.
Observe that
$\mathcal{A}_{\epsilon}(n)=\\{z:\varphi(z,\epsilon,n,\rho_{1}^{n},\ldots,\rho_{d}^{n})\\}$
for a semialgebraic predicate $\varphi$. Viewing $\mathcal{A}_{\epsilon}(n)$
as a proxy for ${\widetilde{\mathcal{O}}}_{\epsilon}(n)$, we arrive at the
following dichotomy.

######  Lemma 3.4.

Either

  1. 1.

for every $\epsilon>0$ there exists $N_{\epsilon}$ such that for all
$n>N_{\epsilon}$, $\mathcal{A}_{\epsilon}(n)$ intersects $S$, or

  2. 2.

there exist $N$ and $\epsilon>0$, both effectively computable, such that
$\mathcal{A}_{\epsilon}(n)$ does not intersect $S$ for all $n>N$.

Moreover, it can be effectively determined which case holds.

######  Proof 3.5.

First we show that the dichotomy holds, putting the issues of effectiveness
aside. Let

$\Phi(\epsilon,n)=\bigvee_{\alpha\in A}\bigwedge_{\beta\in
B}p_{\alpha,\beta}(\epsilon,n,\rho_{1}^{n},\ldots,\rho_{d}^{n})\bowtie_{\alpha,\beta}0$

be a quantifier-free formula equivalent to $\mathcal{A}_{\epsilon}(n)\cap
S\neq\emptyset$. Such $\Phi(\epsilon,n)$ must exist because
$\mathcal{A}_{\epsilon}(n)$ is semialgebraic with parameters from
$\\{\epsilon,n,\rho_{1}^{n},\ldots,\rho_{d}^{n}\\}$ and by the Tarski-
Seidenberg theorem, each such set can be described using a quantifier-free
formula of the form given above. Suppose Case 1 does not hold. Then there
exists a particular $\epsilon>0$ such that $\Phi(\epsilon,n)$ does not hold
for arbitrarily large $n$. Treating $n$ as a continuous parameter, consider
the set $\\{n\in\mathbb{R}_{\geq 0}:\Phi(\epsilon,n)\textrm{ does not
hold}\\}$. By $o$-minimality of ${\mathbb{R}_{\exp}}$ this set is a finite
union of intervals and and by the assumption that Case 1 does not hold, it
contains arbitrarily large integers. Hence it must contain all integers in
$(N,\infty)$ for some $N\in\mathbb{N}$. That is, for all $n>N$ the formula
$\Phi(\epsilon,n)$ does not hold.

Effectiveness.We now address the issues of effectiveness. Consider the formula

$\Psi(\epsilon)=\exists N_{\epsilon}.\,\forall
n>N_{\epsilon}:\Phi(\epsilon,n).$

We show that $\Psi(\epsilon)$ is equivalent to a formula $\psi(\epsilon)$ in
the language of $\mathbb{R}_{0}$. To determine which case holds it then
remains to determine the truth value of the sentence
$\forall\epsilon:\psi(\epsilon)$.

By the $o$-minimality argument above, given $\epsilon>0$, each
$p_{\alpha,\beta}(\epsilon,n,\rho_{1}^{n},\ldots,\rho_{d}^{n})\bowtie_{\alpha,\beta}0$
either holds for finitely many integer values of $n$ or holds for all
sufficiently large integer values $n$. By elementary considerations it follows
that $\Psi(\epsilon)$ is equivalent to

$\bigvee_{\alpha\in A}\bigwedge_{\beta\in B}\,\exists N_{\epsilon}.\,\forall
n>N_{\epsilon}:p_{\alpha,\beta}(\epsilon,n,\rho_{1}^{n},\ldots,\rho_{d}^{n})\bowtie_{\alpha,\beta}0.$

Hence it suffices to show how to construct a formula $\psi(\epsilon)$ in the
language of $\mathbb{R}_{0}$ that is equivalent to $\exists
N_{\epsilon}.\,\forall
n>N_{\epsilon}:p_{\alpha,\beta}(\epsilon,n,\rho_{1}^{n},\ldots,\rho_{d}^{n})\bowtie_{\alpha,\beta}0$.
For each $\epsilon>0$, the formula first tests if $p_{\alpha,\beta}(\epsilon)$
(as a polynomial in $d+1$ remaining variables) is identically zero. If yes,
then $\varphi(\epsilon)$ is true or false depending only on
$\bowtie_{\alpha,\beta}$. Otherwise, write
$p_{\alpha,\beta}(\epsilon,n,\rho_{1}^{n},\ldots,\rho_{d}^{n})=\sum_{i=1}^{k}q_{i}(\epsilon,n)R_{i}^{n}$
where $q_{i}(\epsilon)$ is not identically zero for all $i$ and
$R_{1}>\cdots>R_{k}>0$ are real algebraic numbers of the form
$\rho_{1}^{p_{1}}\cdots\rho_{d}^{p_{d}}$ for
$p_{1},\ldots,p_{d}\in\mathbb{N}$. Since
$\left|q_{1}(\epsilon,n)R_{1}^{n}\right|>\left|\sum_{i=2}^{k}q_{i}(\epsilon,n)R_{i}^{n}\right|$
for sufficiently large $n$, whether
$p_{\alpha,\beta}(\epsilon,n,\rho_{1}^{n},\ldots,\rho_{d}^{n})\bowtie_{\alpha,\beta}0$
holds for sufficiently large $n$ depends only on $q_{1}(\epsilon,n)$. Hence we
can choose $\psi(\epsilon)$ to be
$\lim_{n\to\infty}q_{1}(\epsilon)\bowtie_{\alpha,\beta}0$, which amounts to a
sign condition on the coefficients of $q_{1}(\epsilon,n)$.

Computing $N$. Finally, we show that in Case 2, the value $N$ can be
effectively computed. To this end, by repeatedly trying smaller and smaller
values of $\epsilon$ first compute a rational $e>0$ such that $\Psi(e)$
(equivalently, $\psi(e)$) does not hold. To be able to compute $N$ it then
suffices to compute, for a particular $(\alpha,\beta)$, a value
$N_{\alpha,\beta}$ such that
$p_{\alpha,\beta}(e,n,\rho_{1}^{n},\ldots,\rho_{d}^{n})\bowtie_{\alpha,\beta}0$
does not hold for all $n>N_{\alpha,\beta}$, assuming that it does not hold for
sufficiently large $n$. We can then take $N$ to be the maximum of
$N_{\alpha,\beta}$ over $(\alpha,\beta)\in A\times B$.

To compute $N_{\alpha,\beta}$, consider $p\coloneqq p_{\alpha,\beta}(e)$.
Assuming it is not identically zero (otherwise we can choose
$N_{\alpha,\beta}$ to be any positive integer), write
$p(n,\rho_{1}^{n},\ldots,\rho_{d}^{n})=\sum_{i=1}^{k}q_{i}(n)R_{i}^{n}$ where
$q_{i}$ is not identically zero for all $i$ and $R_{1}>\cdots>R_{k}>0$ are
real algebraic. Since
$p_{\alpha,\beta}(e,n,\rho_{1}^{n},\ldots,\rho_{d}^{n})\bowtie_{\alpha,\beta}0$
and hence $p(n,\rho_{1}^{n},\ldots,\rho_{d}^{n})\bowtie_{\alpha,\beta}0$ do
not hold for sufficiently large $n$, it must be the case that
$q_{1}(n)\bowtie_{\alpha,\beta}0$ does not hold for sufficiently large $n$.
Hence it remains to choose $N_{\alpha,\beta}$ large enough so that for all
$n>N_{\alpha,\beta}$, $|q_{1}(n)R_{1}^{n}|$ dominates
$\left|\sum_{i=2}^{k}q_{i}(n)R_{i}^{n}\right|$.

###  3.3 From the abstraction back to $\epsilon$-pseudo-orbits

In this section we consider the relationship between the two cases of 3.4 and
our original pseudo-reachability problem. We start with Case 2. Observe that
${\mathcal{O}}_{\epsilon}(n)\subseteq\mathcal{A}_{\epsilon}(n)$ for every
$n\in\mathbb{N}$ and $\epsilon>0$. Therefore, when Case 2 holds, for any $n>N$
and $\epsilon>0$ the target set cannot be reached by
${\mathcal{O}}_{\epsilon}$. It remains to check pseudo-reachability at time
steps $n\leq N$. We claim that $S$ is pseudo-reachable if and only

$\forall\epsilon.\,\exists n\leq N:(M^{n}x+cn+d+\epsilon\mathcal{B}(n))\cap
S\neq\emptyset.$

Let $\overline{S}$ denote the topological closure of $S$. We show that the
statement above is equivalent to $\exists n\leq N:M^{n}x+cn+d\in\overline{S}$.
Observe that if for all $n\leq N$ the point $M^{n}x+cn+d$ is not in
$\overline{S}$, then by compactness the smallest distance from
${\\{M^{n}x+cn+d\mid n\leq N\\}}$ to $\overline{S}$ is positive and hence for
sufficiently small $\epsilon$ the target $S$ cannot be $\epsilon$-pseudo-
reached within the first $N$ steps. Conversely, if
$M^{n}x+cn+d\in\overline{S}$ for some $n\leq N$, then because $\mathcal{B}(n)$
is full dimensional and contains ${\mathbf{0}}$ in its interior, it follows
that $(M^{n}x+cn+d+\epsilon\mathcal{B}(n))\cap S\neq\emptyset$ for all
$\epsilon>0$. Therefore, in Case 2 pseudo-reachability can be decided by
simply checking if ${\\{M^{n}x+cn+d\mid n\leq N\\}}$ reaches $\overline{S}$.

Next we will show that $S$ is pseudo-reachable if Case 1 holds. Given
$z\in\mathcal{T}$, we define a “localisation” of the abstraction at the point
$z$ as $\mathcal{A}_{\epsilon}(n)(z):=D^{n}z+cn+d+\epsilon\mathcal{B}(n)$.
Observe that
$\mathcal{A}_{\epsilon}(n)=\\{\mathcal{A}_{\epsilon}(n)(z):z\in\mathcal{T}\\}$.
This definition of a localisation will allow us to select a “concrete
trajectory” from the set of all possible (abstract) trajectories.

Fix $\epsilon>0$ and let
$T_{n}:=\\{z\in\mathcal{T}:\mathcal{A}_{\epsilon}(n)(z)\textrm{ intersects
}S\\}$. The next lemma implies that the sequence $T_{n}$ must tend towards a
limiting shape; i.e. it cannot “jump around” forever.

######  Lemma 3.6.

Let $T_{n}=\\{z:\varphi(z,n,\rho_{1}^{n},\ldots,\rho_{d}^{n})\\}$, where
$\varphi$ is a semialgebraic predicate and $\rho_{1},\ldots,\rho_{d}$ are real
algebraic, be a family of non-empty sets contained in a compact set
$\mathcal{T}$. There exists a non-empty limiting set $L\subseteq\mathcal{T}$
to which the sequence $T_{n}$ converges as $n\to\infty$, in the following
sense.

  1. a

For every $\epsilon>0$, there exists $N$ such that for all $n>N$,
$T_{n}\subseteq L+B({\mathbf{0}},\epsilon)$.

  2. b

For all $z\in L$ and $\epsilon>0$ there exists $N$ such that for all $n>N$,
$z+B({\mathbf{0}},\epsilon)$ intersects $T_{n}$.

######  Proof 3.7.

Write $\varphi(z,n,\rho_{1}^{n},\ldots,\rho_{d}^{n})=\bigvee_{\alpha\in
A}\bigwedge_{\beta\in
B}p_{\alpha,\beta}(z,n,\rho_{1}^{n},\ldots,\rho_{d}^{n})\bowtie_{\alpha,\beta}0$.
We can define the sequence $\langle T_{t}\mid t\in\mathbb{R}\rangle$ as
$T_{t}=\\{z:\varphi(z,t,\rho_{1}^{t},\ldots,\rho_{d}^{t})\\}$. Let
$L=\\{x:\liminf d(x,T_{t})=0\\}$ where $d(x,T_{t})$ denotes the shortest
Euclidean distance from $x$ to a point in $T_{t}$.

We prove the first claim by contradiction. Suppose there exists $\epsilon>0$
such that at infinitely many unbounded time steps $t_{1}<t_{2}<\ldots$ there
are points $z_{1},z_{2},\ldots$ such that $z_{i}\in T_{i}$ but $z_{i}\notin
L+B({\mathbf{0}},\epsilon)$. Then the sequence $z_{i}$ must have an
accumulation point $z$ in $\mathcal{T}\setminus L$. But $z$ will also satisfy
$\liminf d(z,T_{t})=0$ and hence $z\in L$, a contradiction.

We prove the second claim using $o$-minimality of $\mathbb{R}_{\exp}$. Fix
$z\in L$ and $\epsilon>0$ and consider the set
$Z=\\{t\in\mathbb{R}:z+B({\mathbf{0}},\epsilon)\textrm{ intersects }T_{t}\\}$.
The set $Z$ is $o$-minimal, and since $z\in L$, it is unbounded from above.
Hence it must contain an interval of the form $(N,\infty)$, which implies the
desired result.

One can also show that the set $L$ described above is in fact semialgebraic,
but this is not necessary for our arguments. We are now ready to show that $S$
is pseudo-reachable if Case 1 of 3.4 holds.

######  Lemma 3.8.

If for every $\epsilon>0$ there exists $N_{\epsilon}$ such that for all
$n>N_{\epsilon}$, $\mathcal{A}_{\epsilon}(n)$ intersects $S$ then $S$ is
pseudo-reachable.

The main idea of the proof is to use the assumption that
$\mathcal{A}_{\epsilon/2}(n)$ intersects $S$ for sufficiently large $n$ to
construct an $\epsilon$-pseudo-orbit that hits $S$. Intuitively, in order to
simulate $\mathcal{A}_{\epsilon/2}(n)$ using an $\epsilon$-pseudo-orbit,
$\epsilon/2$ of the total control allowance is used to replicate the effect of
the control inputs (of size at most $\epsilon/2$, corresponding to the
$\frac{\epsilon}{2}\mathcal{B}(n)$ term in the definition of
$\mathcal{A}_{\epsilon/2}(n)$) and the remaining $\epsilon/2$ is used to
compensate for the abstraction from the starting point $a$ to the set
$\mathcal{T}$. In fact, we do not know if one can deduce that $S$ is
$\epsilon$-pseudo-reachable from knowing that
$\mathcal{A}_{\epsilon}(n)\textrm{ intersects }S$ for sufficiently large $n$.
This illustrates the reason why the pseudo-reachability problem is easier than
the $\epsilon$-pseudo-reachability problem; see section 4 for a more concrete
argument.

######  Proof 3.9.

Fix $\epsilon>0$. We show how to construct an $\epsilon$-pseudo-orbit that
hits $S$. Consider $\mathcal{A}_{\epsilon/2}(n)$. By assumption, there exists
$N_{1}$ such that for all $n>N_{1}$, $\mathcal{A}_{\epsilon/2}(n)$ intersects
$S$. We now investigate which localisations of the abstraction are responsible
for intersecting $S$. Apply 3.6 to the sequence of sets
$T_{n}=\\{z\in\mathcal{T}:\mathcal{A}_{\epsilon/2}(n)(z)\textrm{ intersects
}S\\}$ to obtain their “limit” $L$. Fix any $p\in L$.

Let $\epsilon^{\prime}$ be small enough so that
$\epsilon^{\prime}D^{n}\mathcal{B}\subseteq\frac{\epsilon}{2}\mathcal{B}(n)$
for all $n>0$. Intuitively, such $\epsilon^{\prime}$ must exist because
$D^{n}\mathcal{B}$ and $D^{n-1}\mathcal{B}$ only differ by at most a constant
factor that only depends on the magnitudes $\rho_{1},\ldots,\rho_{d}$ of
eigenvalues of $M$, and we have that
$D^{n-1}\mathcal{B}\subseteq\sum_{i=0}^{n-1}D^{i}\mathcal{B}=\mathcal{B}(n)$.
By 3.6 (b), there exists $N>N_{1}$ such that for all $n>N$,
$p+B({\mathbf{0}},\epsilon^{\prime}/2)$ intersects $T_{n}$. That is, for all
$n>N$ there exists $p_{n}\in\mathcal{T}$ such that
$||p-p_{n}||<\epsilon^{\prime}/2$ and $p_{n}\in T_{n}$. Equivalently,

$||p-p_{n}||<\epsilon^{\prime}/2\textrm{ and
}\mathcal{A}_{\epsilon/2}(n)(p_{n})\textrm{ intersects }S.$

By Kronecker’s theorem there must exist $m>N$ such that
$||R^{m}x-p||<\epsilon^{\prime}/2$. Hence we have
$||R^{m}x-p_{m}||<\epsilon^{\prime}$ which implies
$R^{m}x-p_{m}\in\epsilon^{\prime}\mathcal{B}$ and hence
$D^{m}(R^{m}x-p_{m})\in\epsilon^{\prime}D^{m}\mathcal{B}$. Since by
construction of $\epsilon^{\prime}$ we have
$\epsilon^{\prime}D^{m}\mathcal{B}\subseteq\frac{\epsilon}{2}\mathcal{B}(m)$,
it follows that $D^{m}(R^{m}x-p_{m})\in\frac{\epsilon}{2}\mathcal{B}(m)$ and
hence $D^{m}p_{m}\in D^{m}R^{m}x+\frac{\epsilon}{2}\mathcal{B}(m)$. Therefore,

${\widetilde{\mathcal{O}}}_{\epsilon}(m)=(D^{m}R^{m}x+\frac{\epsilon}{2}\mathcal{B}(m))+cm+d+\frac{\epsilon}{2}\mathcal{B}(m)\supseteq
D^{m}p_{m}+cm+d+\frac{\epsilon}{2}\mathcal{B}(m)=\mathcal{A}_{\epsilon/2}(m)(p_{m}).$

Since $\mathcal{A}_{\epsilon/2}(m)(p_{m})$ intersects $S$, it then follows
that ${\widetilde{\mathcal{O}}}_{\epsilon}(m)$ too must intersect $S$.

###  3.4 The algorithm

To summarise, the analysis above gives us the following algorithm for
determining if $S$ is pseudo-reachable, i.e. if $\forall\epsilon>0.\,\exists
n:{\widetilde{\mathcal{O}}}_{\epsilon}(n)\cap S\neq\emptyset$. Let
$\varphi(n,\epsilon)$ be a quantifier-free formula in $\mathbb{R}_{\exp}$
defining the abstraction $\mathcal{A}_{\epsilon}(n)$. First determine, using
the algorithm described in the proof of 3.4, whether Case 1 or Case 2 holds.
If the former holds, then conclude that $S$ is pseudo-reachable. If Case 2
holds, then compute the value of $N$ effectively and check if there exists
$n<N$ such that $(M^{n}x+cn+d)\cap\overline{S}\neq\emptyset$.

##  4 Skolem-hardness of the $\epsilon$-pseudo-reachability problem

In this section we consider the $\epsilon$-pseudo-reachability problem for
discrete diagonalisable systems: given diagonalisable $M$, starting point $s$,
a target set $S$ and $\epsilon>0$, decide whether there exists $n$ such that
$M^{n}s+\sum_{k=0}^{n-1}M^{k}B({\mathbf{0}},\epsilon)\cap S\neq 0$. This
problem is also known as the reachability problem for linear time-invariant
systems [8] with the control set $B({\mathbf{0}},\epsilon)$. We will reduce a
hard subclass of the Skolem problem to our $\epsilon$-pseudo-reachability
problem.

The Skolem problem is not known to be decidable for orders $d\geq 5$, even for
diagonalisable recurrences. The largest class of sequences for which
decidability is known is the MSTV (Mignotte-Shorey-Tijdeman-Vereschagin)
class, which consists of all linear recurrence sequences over integers that
(i) have at most three dominant roots with respect to the usual (Archimedean)
absolute or (ii) have at most two dominant roots with respect to a $p$-adic
absolute value [12]. We consider the Skolem problem for integer sequences
whose roots $\rho,\lambda_{1},\ldots,\lambda_{d}$ satisfy
$\rho=|\lambda_{1}|=\cdots=|\lambda_{d}|$. This class of sequences contains
many instances that are not in the MSTV class and hence is a hard subclass of
the Skolem problem.

Recall that any linear recurrence sequence can be written as
$u_{n}=c^{\top}M^{n}s$ where $M$ is the companion matrix of $u_{n}$ whose
eigenvalues are the roots of $u_{n}$. Let $u_{n}$ be a diagonalisable sequence
that belongs to the hard subclass described above, i.e. $u_{n}=c^{\top}M^{n}s$
where $M=\operatorname{diag}(\Lambda_{1},\ldots,\Lambda_{d},\rho)$ and
$\Lambda_{i}$ is a $2\times 2$ real Jordan block with $\rho(\Lambda_{i})=\rho$
for $1\leq i\leq d$. We reduce the problem “does $u_{n}$ have a zero?” to an
$\epsilon$-pseudo-reachability problem.

Consider the sequence $v_{n}=u_{n}^{2}$. Observe that
$v_{n}=\sum_{i=1}^{L}c_{i}\Gamma_{i}^{n}s_{i}+Cr^{n}$ where

  * •

$r=\rho^{2}$,

  * •

$\Gamma_{i}$ is a $2\times 2$ real Jordan block with $\rho(\Gamma_{i})=r$ for
$1\leq i\leq L$,

  * •

$c_{i},s_{i}\in\mathbb{R}^{2}$ for $1\leq i\leq L$, and

  * •

$C>0$.

The first two statements follow from the fact that the eigenvalues of $v_{n}$
are products of eigenvalues of $u_{n}$. That $C>0$ can be deduced as follows.
Consider $w_{n}=\sum_{i=1}^{L}c_{i}\Gamma_{i}^{n}s_{i}$. It only has non-real
roots and hence by [15] is infinitely often positive and negative. Hence if
$C$ is not positive, then $v_{n}<0$ for infinitely many $n$, which contradicts
the fact that $v_{n}\geq 0$.

Next observe that $u_{n}$ has a zero iff there exists $n$ such that $v_{n}\leq
0$. Since we are interested only in the sign of $v_{n}$, by scaling $v_{n}$ by
$C(2r)^{n}$ if necessary we assume that $r\in(0,1)$ and $C=1$. We will
construct an instance of the $\epsilon$-pseudo-reachability problem that is
positive if and only if there exists $n$ such that $v_{n}\leq 0$.

Define

  * •

$A=\operatorname{diag}(\Gamma_{1},\ldots,\Gamma_{L})$,

  * •

$s=(s_{1},\ldots,s_{L})$ and $c=(c_{1},\ldots,c_{L})$,

  * •

$\epsilon=\frac{1-r}{||c||}$, and

  * •

$H=\\{z:c^{\top}\cdot z+1\leq 0\\}$.

Observe that $H$ is $\epsilon$-pseudo-reachable if and only if
$A^{n}s+\sum_{i=0}^{n-1}A^{i}B({\mathbf{0}},\epsilon)\cap H\neq 0$ for some
$n$. Since $A^{i}B({\mathbf{0}},\epsilon)=B({\mathbf{0}},r^{i}\epsilon)$, we
have
$\sum_{i=0}^{n-1}A^{i}B({\mathbf{0}},\epsilon)=B({\mathbf{0}},\frac{1-r^{n}}{1-r}\epsilon)\coloneqq\mathcal{B}(n)$
and

$\textrm{$H$ is $\epsilon$-pseudo-reachable
}\iff\min_{z\in\mathcal{B}(n)}c\cdot(A^{n}s+z)+1\textrm{ is $\leq 0$ for some
$n$.}$

We will show that in fact $\min_{z\in\mathcal{B}(n)}c\cdot(A^{n}s+z)+1=v_{n}$,
which will conclude the proof.

$\begin{split}\min_{z\in\mathcal{B}(n)}c\cdot(A^{n}s+z)+1&=\sum_{i=1}^{L}c_{i}\Gamma_{i}^{n}s_{i}+1+\min_{z\in\mathcal{B}(n)}c\cdot
z\\\
&=\sum_{i=1}^{L}c_{i}\Gamma_{i}^{n}s_{i}+1-||c||\frac{1-r^{n}}{1-r}\epsilon\\\
&=\sum_{i=1}^{L}c_{i}\Gamma_{i}^{n}s_{i}+r^{n}\\\ &=v_{n}.\end{split}$

##  5 The continuous-time pseudo-reachability problem

In this section we show that the approach we described in section 3 for
deciding the discrete-time pseudo-reachability problem for diagonalisable
systems also works in the continuous setting with one important difference: to
handle Case 2 of the dichotomy lemma (exactly the same as 3.4) we need to
solve the _bounded-time reachability problem for continuous-time affine
dynamical systems_ , which is only known to be decidable assuming Schanuel’s
conjecture [5]. For detailed proofs see the full version of the paper.

Let
$M=\operatorname{diag}(\Lambda_{1},\ldots,\Lambda_{k},\rho_{k+1},\ldots,\rho_{d})\in(\mathbb{R}\cap{\overline{\mathbb{Q}}})^{L\times
L}$ be a diagonalisable matrix in real Jordan form, $s\in\mathbb{Q}^{L}$ be a
starting point, $b\in\mathbb{Q}^{L}$ be an affine term and
$S\subseteq\mathbb{R}^{L}$ be a semialgebraic target set. The trajectory of
the system (in the absence of additional control inputs) is given by

$x(t)=e^{Mt}s+\int_{0}^{t}e^{Mh}b\,dh.$

Intuitively, while in the discrete setting control inputs are applied after
each unit of time and thus are represented by a sequence $\langle d_{n}\mid
n\in\mathbb{N}\rangle$, in the continuous setting they are represented by a
continuous function $\Delta:\mathbb{R}_{\geq 0}\to\mathbb{R}^{L}$. Hence an
$\epsilon$-pseudo-orbit is defined as a trajectory

$x(t)=e^{Mt}s+\int_{0}^{t}e^{Mh}b\,\,dh+\int_{0}^{t}e^{Mh}\Delta(t-h)\,dh.$

for some control signal $\Delta:\mathbb{R}_{\geq 0}\to\mathbb{R}^{L}$
satisfying $||\Delta_{\epsilon}(t)||\leq\epsilon$ for all $t\geq 0$. The
pseudo-reachability problem is then defined in the same way as before: decide
whether for every $\epsilon>0$ there exists an $\epsilon$-pseudo-orbit that
reaches $S$.

Let $\mathcal{B}$ be the same control set as defined in subsection 3.1. For
$1\leq j\leq k$, let $r_{j}=\operatorname{Re}(\lambda_{j})$ and
$\omega_{j}=\operatorname{Im}(\lambda_{j})$ where $\lambda_{j}$ is a non-real
eigenvalue of the block $\Lambda_{j}$. For $k<j\leq d$ let $r_{j}=\rho_{j}$
and $\omega_{j}=0$. By using essentially the same arguments as in subsection
3.1, we can show that the pseudo-reachability problem is equivalent to
determining the truth of

$\forall\epsilon>0.\,\exists t:(e^{Mt}x+ct+d+\epsilon\mathcal{B}(t))\cap
S\neq\emptyset$

where $x,c,d$ are $L$-dimensional vectors and
$\mathcal{B}(t)=\\{z:\varphi(z,t,e^{r_{1}t},\ldots,e^{r_{d}t})\\}$ for
semialgebraic predicate $\varphi$. We denote the term
$e^{Mt}x+ct+d+\mathcal{B}(t)$ by ${\widetilde{\mathcal{O}}}_{\epsilon}(n)$.

To define a convenient abstraction, we again write $e^{Mt}=D(t)R(t)$ where
$D(t)\coloneqq\operatorname{diag}(e^{r_{1}t},e^{r_{1}t},\dots,e^{r_{k}t},e^{r_{k}t},e^{r_{k+1}t},e^{r_{k+2}t},\dots,e^{r_{k+d}t})$
is diagonal and $R(t)$ is a block diagonal matrix whose blocks are rotation
matrices of the form $\begin{bmatrix}\cos(\omega_{j}t)&-\sin(\omega_{i}t)\\\
\sin(\omega_{j}t)&\cos(\omega_{j}t)\end{bmatrix}$ for $1\leq j\leq k$ and are
of the form $\Omega_{i}=\begin{bmatrix}1\end{bmatrix}$ for $k+1\leq j\leq d$.
Just as in the discrete case, we next define

$\mathcal{T}\coloneqq\operatorname{cl}(\\{R(t)x:t\in\mathbb{R}_{\geq
0}\\})\textrm{ and }\mathcal{A}_{\epsilon}(t)\coloneqq
D(t)\mathcal{T}+ct+d+\epsilon\mathcal{B}(t),$

where $\mathcal{T}$ is again semialgebraic and effectively computable [5] and
$\mathcal{A}_{\epsilon}$ acts as an abstraction of
${\widetilde{\mathcal{O}}}_{\epsilon}$. In particular, for all $\epsilon>0$
and $t\in\mathbb{R}_{\geq 0}$, we have
${\widetilde{\mathcal{O}}}_{\epsilon}(t)\subseteq\mathcal{A}_{\epsilon}(t)$.
Moreover, observe that
$\mathcal{A}_{\epsilon}(t)=\varphi(t,e^{r_{1}t},\ldots,e^{r_{d}t})$ for a
semialgebraic function $\varphi$, which is the most important property we
need. We use $\mathcal{A}_{\epsilon}(t)$ in the same way we used
$\mathcal{A}_{\epsilon}(n)$ in the discrete case to arrive at the following
dichotomy lemma.

######  Lemma 5.1.

Either

  1. 1.

for every $\epsilon>0$ there exists $T_{\epsilon}$ such that for all
$t>T_{\epsilon}$, $\mathcal{A}_{\epsilon}(t)$ intersects $S$, or

  2. 2.

there exist $T$ and $\epsilon>0$, both effectively computable, such that
$\mathcal{A}_{\epsilon}(t)$ does not intersect $S$ for all $t>T$.

Moreover, it can be effectively determined which case holds.

######  Proof 5.2.

First we show that the dichotomy holds, putting the issues of effectiveness
aside. Let

$\Phi(\epsilon,t)=\bigvee_{\alpha\in A}\bigwedge_{\beta\in
B}p_{\alpha,\beta}(\epsilon,t,e^{r_{1}t},\ldots,e^{r_{d}t})\bowtie_{\alpha,\beta}0$

be a quantifier-free formula equivalent to $\mathcal{A}_{\epsilon}(n)\cap
S\neq\emptyset$. Suppose Case 1 does not hold. Then there exists a particular
$\epsilon>0$ such that $\Phi(\epsilon,t)$ does not hold for arbitrarily large
$t$. Consider the set $\\{t\geq 0:\Phi(\epsilon,t)\textrm{ does not hold}\\}$.
By $o$-minimality of ${\mathbb{R}_{\exp}}$ this set is a finite union of
intervals and since it contains arbitrarily large real numbers by assumption,
it must contain an unbounded interval $(T,\infty)$. That is, for all $t>T$ the
formula $\Phi(\epsilon,t)$ does not hold.

Effectiveness.We now address the issues of effectiveness. Consider the formula

$\Psi(\epsilon)=\exists T_{\epsilon}.\,\forall
t>T_{\epsilon}:\Phi(\epsilon,t).$

We show that $\Psi(\epsilon)$ is equivalent to a formula $\psi(\epsilon)$ in
the language of $\mathbb{R}_{0}$. To determine which case holds it then
remains to determine the truth value of the sentence
$\forall\epsilon:\psi(\epsilon)$.

By the $o$-minimality argument above, given $\epsilon>0$, each the values of
$t$ for which
$p_{\alpha,\beta}(\epsilon,t,e^{r_{1}t},\ldots,e^{r_{d}t})\bowtie_{\alpha,\beta}0$
holds is either bounded or contains an unbounded interval. By elementary
considerations it follows that $\Psi(\epsilon)$ is equivalent to

$\bigvee_{\alpha\in A}\bigwedge_{\beta\in B}\,\exists T_{\epsilon}.\,\forall
t>T_{\epsilon}:p_{\alpha,\beta}(\epsilon,t,e^{r_{1}t},\ldots,e^{r_{d}t})\bowtie_{\alpha,\beta}0.$

Hence it suffices to show how to construct a formula in the language of
$\mathbb{R}_{0}$ that is equivalent to $\exists T_{\epsilon}.\,\forall
t>T_{\epsilon}:p_{\alpha,\beta}(\epsilon,t,e^{r_{1}t},\ldots,e^{r_{d}t})\bowtie_{\alpha,\beta}0$.
For each $\epsilon>0$, the formula first tests if $p_{\alpha,\beta}(\epsilon)$
(as a polynomial in $d+1$ remaining variables) is identically zero. If yes,
then $\varphi(\epsilon)$ is true or false depending only on
$\bowtie_{\alpha,\beta}$. Otherwise, write
$p_{\alpha,\beta}(\epsilon,t,e^{r_{1}t},\ldots,e^{r_{d}t})=\sum_{i=1}^{k}q_{i}(\epsilon,n)R_{i}^{n}$
where $q_{i}(\epsilon)$ is not identically zero for all $i$ and
$R_{1}>\cdots>R_{k}>0$ are of the form $e^{p_{1}r_{1}+\ldots+p_{d}r_{d}}$ for
$p_{1},\ldots,p_{d}\in\mathbb{N}$. Since
$\left|q_{1}(\epsilon,n)R_{1}^{n}\right|>\left|\sum_{i=2}^{k}q_{i}(\epsilon,n)R_{i}^{n}\right|$
for sufficiently large $n$, whether
$p_{\alpha,\beta}(\epsilon,n,\rho_{1}^{n},\ldots,\rho_{d}^{n})\bowtie_{\alpha,\beta}0$
holds for sufficiently large $n$ depends only on $q_{1}(\epsilon,n)$. Hence we
can choose $\psi(\epsilon)$ to be
$\lim_{n\to\infty}q_{1}(\epsilon)\bowtie_{\alpha,\beta}0$, which amounts to a
sign condition on the coefficients of $q_{1}(\epsilon,n)$.

Computing $T$. Finally, we show that in Case 2, the value $T$ can be
effectively computed. To this end, by repeatedly trying smaller and smaller
values of $\epsilon$ first compute a rational $e>0$ such that $\Psi(e)$
(equivalently, $\psi(e)$) does not hold. To be able to compute $T$ it then
suffices to compute, for a particular $(\alpha,\beta)$, a value
$T_{\alpha,\beta}$ such that
$p_{\alpha,\beta}(\epsilon,t,e^{r_{1}t},\ldots,e^{r_{d}t})\bowtie_{\alpha,\beta}0$
does not hold for all $t>T_{\alpha,\beta}$, assuming that it does not hold for
sufficiently large $t$. We can then take $T$ to be the maximum of
$T_{\alpha,\beta}$ over $(\alpha,\beta)\in A\times B$.

To compute $T_{\alpha,\beta}$, consider $p\coloneqq p_{\alpha,\beta}(e)$.
Assuming it is not identically zero (otherwise we can choose
$T_{\alpha,\beta}$ to be any positive integer), write
$p(t,e^{r_{1}t},\ldots,e^{r_{d}t})=\sum_{i=1}^{k}q_{i}(n)R_{i}^{n}$ where
$q_{i}$ is not identically zero for all $i$ and $R_{1}>\cdots>R_{k}>0$ are of
the form $e^{p_{1}r_{1}+\ldots+p_{d}r_{d}}$ for
$p_{1},\ldots,p_{d}\in\mathbb{N}$. Since
$p_{\alpha,\beta}(\epsilon,t,e^{r_{1}t},\ldots,e^{r_{d}t})\bowtie_{\alpha,\beta}0$
and hence $p(t,e^{r_{1}t},\ldots,e^{r_{d}t})\bowtie_{\alpha,\beta}0$ do not
hold for sufficiently large $n$, it must be the case that
$q_{1}(n)\bowtie_{\alpha,\beta}0$ does not hold for sufficiently large $n$.
Hence it remains to choose $N_{\alpha,\beta}$ large enough so that for all
$n>N_{\alpha,\beta}$, $|q_{1}(n)R_{1}^{n}|$ dominates
$\left|\sum_{i=2}^{k}q_{i}(n)R_{i}^{n}\right|$.

We next show pseudo-reachability in Case 1.

######  Lemma 5.3.

If for every $\epsilon>0$ there exists $T_{\epsilon}$ such that for all
$t>T_{\epsilon}$, $\mathcal{A}_{\epsilon}(t)$ intersects $S$ then $S$ is
pseudo-reachable.

######  Proof 5.4.

We first define a suitable notion of localisation, in exacty the same way as
the discrete case. Given $z\in\mathbb{T}$, let
$\mathcal{A}_{\epsilon}(t)(z)=D(t)z+ct+d+\epsilon\mathcal{B}(t)$.

Fix $\epsilon>0$. We show how to construct an $\epsilon$-pseudo-orbit that
hits $S$. In fact, this $\epsilon$-pseudo-orbit will hit $S$ at an integer
time step $m$. Consider $\mathcal{A}_{\epsilon/2}(t)$. By assumption, there
exists $T_{1}$ such that for all $t>T_{1}$, $\mathcal{A}_{\epsilon/2}(t)$
intersects $S$. We now investigate which localisations of the abstraction are
responsible for intersecting $S$. Apply 3.6 to the sets
$T_{n}=\\{z\in\mathcal{T}:\mathcal{A}_{\epsilon/2}(n)(z)\textrm{ intersects
}S\\}$, $n\in\mathbb{N}$, to obtain their ‘limit’ $L$. Fix any $p\in L$.

Let $\epsilon^{\prime}$ be small enough so that for all $n>0$,
$\epsilon^{\prime}D(n)B({\mathbf{0}},1)\subseteq\frac{\epsilon}{2}\mathcal{B}(n)$.
By 3.6 (b), there exists $N>T_{1}$ such that for all integers $n>N$,
$p+B({\mathbf{0}},\epsilon^{\prime}/2)$ intersects $T_{n}$. That is, for all
$n>N$ there exists $p_{n}\in\mathcal{T}$ such that
$||p-p_{n}||<\epsilon^{\prime}/2$ and $p_{n}\in T_{n}$. Equivalently,

$||p-p_{n}||<\epsilon^{\prime}/2\textrm{ and
}\mathcal{A}_{\epsilon/2}(n)(p_{n})\textrm{ intersects }S.$

By Kronecker’s theorem there must exist integer $m>N$ such that
$||R(m)x-p||<\epsilon^{\prime}/2$. Hence we have
$||R(m)x-p_{m}||<\epsilon^{\prime}$ which implies
$R(m)x-p_{m}\in\epsilon^{\prime}B({\mathbf{0}},1)$ and hence
$D(m)(R(m)x-p_{m})\in\epsilon^{\prime}D(m)B({\mathbf{0}},1)$. Since by
construction of $\epsilon^{\prime}$ we have
$\epsilon^{\prime}D(m)\mathcal{B}({\mathbf{0}},1)\subseteq\frac{\epsilon}{2}\mathcal{B}(m)$,
it follows that $D(m)(R(m)x-p_{m})\in\frac{\epsilon}{2}\mathcal{B}(m)$ and
hence $D(m)p_{m}\in D(m)R(m)x+\frac{\epsilon}{2}\mathcal{B}(m)$. Therefore,

$\displaystyle{\widetilde{\mathcal{O}}}_{\epsilon}(m)$
$\displaystyle=\left(D(m)R(m)x+\frac{\epsilon}{2}\mathcal{B}(m)\right)+cm+d+\frac{\epsilon}{2}\mathcal{B}(m)$
$\displaystyle\supseteq D(m)p_{m}+cm+d+\frac{\epsilon}{2}\mathcal{B}(m)$
$\displaystyle=\mathcal{A}_{\epsilon/2}(m)(p_{m}).$

Since $\mathcal{A}_{\epsilon/2}(m)(p_{m})$ intersects $S$, it then follows
that ${\widetilde{\mathcal{O}}}_{\epsilon}(m)$ too must intersect $S$.

We thus have reduced the pseudo-reachability problem to that of handling Case
2:

######  Theorem 5.5.

The continuous-time pseudo-reachability problem reduces to the bounded-time
reachability problem for continuous-time affine dynamical systems.

Intuitively, the dichotomy lemma (3.4) holds verbatim for the continuous
systems, and in Case 1 again $S$ is always pseudo-reachable. It then remains
to handle Case 2. Since bounded-time reachability problem for continuous-time
affine dynamical systems can be encoded in
$\mathbb{R}_{\exp,\cos{\upharpoonright}[0,T]}$, we have the following
(conditional) decidability result.

######  Corollary 5.6.

Continuous-time pseudo-reachability problem for diagonalisable affine
dynamical systems is decidable subject to Schanuel’s conjecture.

##  6 Discussion

The main technical result of our paper is that it is decidable whether

$\forall\epsilon>0.\,\exists
n:\,\left(M^{n}x+f(n)+\epsilon\mathcal{B}(n)\right)\cap S\neq 0$

where $M$ is a diagonalisable matrix with algebraic entries, $x$ is an
algebraic starting point, $f$ is a semialgebraic function, $S$ is a
semialgebraic target and
$\mathcal{B}(n)=\varphi(n,\rho_{1}^{n},\ldots,\rho_{d}^{n})$ for
$\rho_{1},\ldots,\rho_{d}\in\mathbb{R}\cap{\overline{\mathbb{Q}}}$ and a
semialgebraic function $\varphi$. We used this result to show decidability of
the discrete-time pseudo-reachability problem for diagonalisable systems in
the following way. We first observed that the pseudo-reachability problem can
be cast as the problem of determining whether $\forall\epsilon>0.\,\exists
n:{\widetilde{\mathcal{O}}}_{\epsilon}(n)\cap S\neq\emptyset$, where
${\widetilde{\mathcal{O}}}_{\epsilon}(n)$ is the set of all points that are
reachable exactly at the time $n$ via an $\epsilon$-pseudo-orbit. After
choosing $\mathcal{B}$ as the most convenient control set (see 3.2 and
subsection 3.1), we then showed that ${\widetilde{\mathcal{O}}}_{\epsilon}(n)$
can be written as $M^{n}x+f(n)+\epsilon\mathcal{B}(n)$.

The reason we are unable to show decidability for non-diagonalisable systems
in this fashion is that we are unable to write
${\widetilde{\mathcal{O}}}_{\epsilon}(n)$ as
$M^{n}x+f(n)+\epsilon\mathcal{B}(n)$. For example, already for the Jordan
block $M=\begin{bmatrix}1&1\\\ 0&1\end{bmatrix}$, and in general already for
blocks with a single repeated real eigenvalue, we do not know whether it is
even possible to eliminate the summation $\sum_{i=0}^{n-1}M^{i}B$ and express
${\widetilde{\mathcal{O}}}_{\epsilon}(n)=M^{n}x+\epsilon\sum_{i=0}^{n-1}M^{i}B$,
where $B$ is any full dimensional shape containing ${\mathbf{0}}$ in its
interior, in the required fashion.

Our approach, however, can be used to solve, in full generality, the robre ust
reachability problem of [1]: given $M,x$ and $S$, decide whether
$\forall\epsilon>0:\,\exists n:\,(M^{n}x+\epsilon M^{n}B({\mathbf{0}},1))\cap
S\neq\emptyset$. Intuitively, the reason is that in this version there is no
summation of the form $\sum_{i=0}^{n-1}M^{i}B$. Detailed proofs (for both the
discrete-time and the continuous-time versions) can be found in the appendix.
For diagonalisable systems in particular, decidability of the robust
reachability problem is almost immediate. First, one can again show that the
problem is equivalent to determining whether $\forall\epsilon>0:\,\exists
n:\,(M^{n}x+\epsilon M^{n}\mathcal{B})\cap S\neq\emptyset$. It then remains to
observe that $M^{n}\mathcal{B}=\varphi(n,\rho_{1}^{n},\ldots,\rho_{d}^{n})$
for a semialgebraic predicate $\varphi$ and apply the technical result
described above.

## References

  * [1] S. Akshay, Hugo Bazille, Blaise Genest, and Mihir Vahanwala.  On Robustness for the Skolem and Positivity Problems.  In Petra Berenbrink and Benjamin Monmege, editors, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022), volume 219 of Leibniz International Proceedings in Informatics (LIPIcs), pages 5:1–5:20, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  URL: https://drops.dagstuhl.de/opus/volltexte/2022/15815, doi:10.4230/LIPIcs.STACS.2022.5.
  * [2] Dmitri V. Anosov.  Geodesic flows on closed Riemannian manifolds of negative curvature.  Proc. Steklov Inst. Math., 90, 1967.
  * [3] Corentin Barloy, Nathanaël Fijalkow, Nathan Lhote, and Filip Mazowiecki.  A Robust Class of Linear Recurrence Sequences.  In Maribel Fernández and Anca Muscholl, editors, 28th EACSL Annual Conference on Computer Science Logic (CSL 2020), volume 152 of Leibniz International Proceedings in Informatics (LIPIcs), pages 9:1–9:16, Dagstuhl, Germany, 2020. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.  URL: https://drops.dagstuhl.de/opus/volltexte/2020/11652, doi:10.4230/LIPIcs.CSL.2020.9.
  * [4] Rufus Bowen.  Equilibrium States and the Ergodic Theory of Anosov Diffeomorphisms, volume 470 of Lecture Notes in Mathematics.  Springer-Verlag, 1975.
  * [5] Ventsislav Chonev, Joël Ouaknine, and James Worrell.  On the Skolem Problem for Continuous Linear Dynamical Systems.  In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), volume 55 of Leibniz International Proceedings in Informatics (LIPIcs), pages 100:1–100:13, Dagstuhl, Germany, 2016. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.  URL: http://drops.dagstuhl.de/opus/volltexte/2016/6235, doi:10.4230/LIPIcs.ICALP.2016.100.
  * [6] Charles C. Conley.  Isolated invariant sets and the Morse index, volume 25 of CBMS Regional Conference Series in Mathematics.  American Mathematical Society, 1978.
  * [7] Julian D’Costa, Toghrul Karimov, Rupak Majumdar, Joël Ouaknine, Mahmoud Salamati, Sadegh Soudjani, and James Worrell.  The Pseudo-Skolem Problem is Decidable.  In Filippo Bonchi and Simon J. Puglisi, editors, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021), volume 202 of Leibniz International Proceedings in Informatics (LIPIcs), pages 34:1–34:21, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  URL: https://drops.dagstuhl.de/opus/volltexte/2021/14474, doi:10.4230/LIPIcs.MFCS.2021.34.
  * [8] Nathanaël Fijalkow, Joël Ouaknine, Amaury Pouly, João Sousa-Pinto, and James Worrell.  On the decidability of reachability in linear time-invariant systems.  In Proceedings of the 22nd ACM International Conference on Hybrid Systems: Computation and Control, HSCC ’19, page 77–86, New York, NY, USA, 2019. Association for Computing Machinery.  doi:10.1145/3302504.3311796.
  * [9] Godfrey H. Hardy and Edward M. Wright.  An Introduction to the Theory of Numbers.  Oxford University Press, 1999.
  * [10] Toghrul Karimov, Engel Lefaucheux, Joël Ouaknine, David Purser, Anton Varonka, Markus A. Whiteland, and James Worrell.  What’s decidable about linear loops?  Proc. ACM Program. Lang., 6(POPL), jan 2022.  doi:10.1145/3498727.
  * [11] Serge Lang.  Introduction to transcendental numbers.  Addison-Wesley series in mathematics. Addison-Wesley Pub. Co., 1966.
  * [12] Richard Lipton, Florian Luca, Joris Nieuwveld, Joël Ouaknine, and David Purser James Worrell.  On the skolem problem and the skolem conjecture.  To appear in LICS 2022.  URL: https://people.mpi-sws.org/~joel/publications/skolem_five22.pdf.
  * [13] Angus Macintyre and Alex J. Wilkie.  On the decidability of the real exponential field.  In Piergiorgio Odifreddi, editor, Kreiseliana. About and Around Georg Kreisel, pages 441–467. A K Peters, 1996.
  * [14] David W. Masser.  Linear relations on algebraic groups.  In New Advances in Transcendence Theory. Camb. Univ. Press, 1988\.
  * [15] Kenji Nagasaka and Jau-Shyong Shiue.  Asymptotic positiveness of linear recurrence sequences.  Fibonacci Quart, 28(4):340–346, 1990.
  * [16] Joël Ouaknine and James Worrell.  Positivity problems for low-order linear recurrence sequences.  In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 366–379, 2014.
  * [17] Joël Ouaknine and James Worrell.  On linear recurrence sequences and loop termination.  ACM SIGLOG News, 2(2):4–13, apr 2015.  doi:10.1145/2766189.2766191.
  * [18] L. P. D. van den Dries.  Tame Topology and O-minimal Structures.  Cambridge University Press, 1998.
  * [19] A. J. Wilkie.  Schanuel’s conjecture and the decidability of the real exponential field.  In Bradd T. Hart, Alistair H. Lachlan, and Matthew A. Valeriote, editors, Algebraic Model Theory, pages 223–230. Springer Netherlands, Dordrecht, 1997.

##  Appendix A Discrete robust reachability problem

In this section, we show the full decidability (including for non-
diagonalisable systems) of the discrete-time robust reachability problem:
decide, given $M\in(\mathbb{R}\cap{\overline{\mathbb{Q}}})^{L\times L}$, a
starting point $x\in\mathbb{Q}^{L}$ and a target $S\subseteq\mathbb{R}^{L}$,
whether for every $\epsilon>0$ there exists $n$ and $\delta\in
B(0,\epsilon)=\epsilon B({\mathbf{0}},1)$ such that $M^{n}(x+\delta)\in S$. As
discussed in section 3, wlog we can assume that $M$ is in real Jordan form:

$M=\operatorname{diag}(J_{1},\ldots J_{k},J_{k+1},\ldots,J_{d})$

where for $1\leq i\leq k$ the block $J_{i}$ has two non-real eigenvalues and
for $k<i\leq d$ the block $J_{i}$ has one real eigenvalue. We denote the
multiplicity and the spectral radius of $J_{i}$ by $\sigma_{i}$ and
$\rho_{i}$, respectively.

As discussed in section 3, the robust reachability problem can be equivalently
stated in terms of any full-dimensional set $\mathcal{B}$ that contains
${\mathbf{0}}$ in its interior (instead of $B({\mathbf{0}},1)$) as the
“control set”. That is, for any such set $\mathcal{B}$, the problem of
deciding whether $\forall\epsilon.\,\exists n:(M^{n}x+\epsilon
M^{n}\mathcal{B})\cap S\neq\emptyset$ is equivalent to the robust reachability
problem. We first give a set $\mathcal{B}$ that is most appropriate for our
purposes. Intuitively, the idea is again to eliminate the rotations in $M^{n}$
so that $M^{n}\mathcal{B}$ can be defined in a first-order fashion using
algebraic parameters. Let $\mathcal{B}=\Pi_{i=1}^{d}\mathcal{B}_{i}$ where (i)
$\mathcal{B}_{i}=\Pi_{j=1}^{\sigma_{i}}B((0,0),1)$ for $1\leq i\leq k$ and
(ii) $B_{i}=[-1,1]^{\sigma_{i}}$ for $k<i\leq d$. Define
$\mathcal{B}(n)=M^{n}\mathcal{B}$ and observe that

$\mathcal{B}(n)=\varphi(n,\rho_{1}^{n},\ldots,\rho_{d}^{n})$

where $\varphi$ is a semialgebraic function. Let
${\widetilde{\mathcal{O}}}_{\epsilon}(n)=M^{n}x+\epsilon\mathcal{B}(n)$. The
robust reachability problem is then equivalent to determining whether

$\forall\epsilon>0.\,\exists n:\,{\widetilde{\mathcal{O}}}_{\epsilon}(n)\cap
S\neq\emptyset.$

We move onto defining the abstraction for $M^{n}x$. Assume $M$ is of the same
form as above. For $\alpha\in\mathbb{T}$ let
$R(\alpha)=\begin{bmatrix}\operatorname{Re}(\alpha)&-\operatorname{Im}(\alpha)\\\
\operatorname{Im}(\alpha)&\operatorname{Re}(\alpha)\end{bmatrix}$ and for
$1\leq i\leq k$ let $\gamma_{i}=\lambda_{i}/\rho(J_{i})$ for a non-real
eigenvalue $\lambda_{i}$ of the block $J_{i}$. Let
$f:\mathbb{N}\times\mathbb{T}^{k}\to\mathbb{R}^{L\times L}$ be the “matrix
builder” function, defined as follows.

$f(n,(\alpha_{1},\ldots,\alpha_{k}))=\operatorname{diag}(g(\alpha_{1}),\ldots,g(\alpha_{k}),J_{k+1}^{n},\ldots,J_{d}^{n}),$
(1)

where

$g(\alpha_{i})=\begin{bmatrix}A_{i}&n\Lambda_{i}^{-1}A_{i}&\cdots&\binom{n}{\sigma_{i}-1}\Lambda_{i}^{-\sigma_{i}+1}A_{i}\\\
&A_{i}&\ddots&\vdots\\\ &&\ddots&n\Lambda_{i}^{-1}A_{i}\\\
&&&A_{i}\end{bmatrix}\textrm{ and }A_{i}=\rho_{i}^{n}R(\alpha).$

We define the matrix builder with respect to the state matrix $M$ which is
given in real JNF. For example, for $\alpha,\beta\in\mathbb{T}$ and the state
matrix

$M=\begin{bmatrix}\Lambda_{1}&I\\\ &\Lambda_{1}&\\\ &&\Lambda_{2}&I\\\
&&&\Lambda_{2}\\\ &&&&\rho_{3}&1\\\ &&&&&\rho_{3}\end{bmatrix},$

the corresponding matrix builder takes the form

$f(n,(\alpha,\beta))=\begin{bmatrix}A&n\Lambda_{1}^{-1}A\\\ &A&\\\
&&B&n\Lambda_{2}^{-1}B\\\ &&&B\\\ &&&&\rho_{3}^{n}&n\\\
&&&&&\rho_{3}^{n}\end{bmatrix}.$

Here $A=\rho(\Lambda_{1})^{n}R(\alpha)$ and $B=\rho(\Lambda_{2})^{n}R(\beta)$.
Let

$\mathcal{T}=\operatorname{cl}(\\{(\gamma_{1}^{n},\ldots,\gamma_{k}^{n}):n\in\mathbb{N}\\}).$

The set $\mathcal{T}$ is semialgebraic and effectively computable. Further
define

$\mathcal{A}_{\epsilon}(n)(z)=f(n,z)x+\epsilon\mathcal{B}(n)\textrm{ and
}\mathcal{A}_{\epsilon}(n)=\\{\mathcal{A}_{\epsilon}(n)(z):z\in\mathcal{T}\\}.$

Then $M^{n}x=f(n,(\gamma_{1}^{n},\ldots,\gamma_{k}^{n}))x$ is abstracted by
$\\{f(n,z)x:z\in\mathbb{T}^{k}\\}$ and
$\mathcal{A}_{\epsilon}(n)\supseteq{\widetilde{\mathcal{O}}}_{\epsilon}(n)$.

The following lemma encapsulates all the nasty differences between the
diagonalisable and the non-diagonalisable case. Its proof is an easy
manipulation of matrices.

######  Lemma A.1.

Given $z=(\alpha_{1},\ldots,\alpha_{k})$, a time step $n$, an update matrix
$M$ and a starting point $x$,

$f(n,(\alpha_{1},\ldots,\alpha_{k}))x=M^{n}x+M^{n}\Delta$

has a solution

$\Delta=(\Delta_{1},\ldots,\Delta_{k},{\mathbf{0}},\ldots,{\mathbf{0}})$

where
$\Delta_{i}(j)=R(\gamma_{i}^{-n})(R(\alpha_{i})-R(\gamma_{i}^{n}))x_{i}(j)$
for $1\leq i\leq k$ and $1\leq j\leq\sigma_{i}$.

Observe that, assuming $k$ and $x$ are fixed,
$||\Delta||=O(||z-\Gamma^{n}||)$, where
$\Gamma^{n}=(\gamma_{1}^{n},\ldots,\gamma_{k}^{n})$. Hence we obtain the
following corollary, which intuitively states that if $z$ is close to
$\Gamma^{n}$, then $f(n,z)x$ is close to the true point $M^{n}x$, in the sense
that $f(n,z)x$ can be reached from $x$ by first jumping to a point
$x^{\prime}$ that is at most $\epsilon\mathcal{B}$ away and then applying $M$
exactly $n$ times.

######  Corollary A.2.

Given $M$ and $x$, there exists $C$ such that for all $\epsilon>0$ and
$z\in\mathbb{T}^{k}$,

$||\Gamma^{n}-z||<C\epsilon\implies\exists\Delta\in\epsilon\mathcal{B}:\,f(n,z)x=M^{n}x+M^{n}\Delta.$

We now move onto proving decidability of the robust reachability problems.
Firstly, the dichotomy lemma and its proof hold verbatim.

######  Lemma A.3.

Either

  1. 1.

for every $\epsilon>0$ there exists $N_{\epsilon}$ such that for all
$n>N_{\epsilon}$, $\mathcal{A}_{\epsilon}(n)$ intersects $S$, or

  2. 2.

there exist computable $N$ and $\epsilon>0$ such that
$\mathcal{A}_{\epsilon}(n)$ does not intersect $S$ for all $n>N$.

Moreover, it can be effectively determined which case holds.

If Case 1 holds, then $S$ is robust reachable if and only if it is reachable
within the first $N$ steps. We will show that in Case 2 $S$ is robust
reachable. This will conclude the proof.

######  Lemma A.4.

If for all $\epsilon>0$ there exists $N_{\epsilon}$ such that for all
$n>N_{\epsilon}$, $\mathcal{A}_{\epsilon}(n)$ intersects $S$ then $S$ is
robust reachable.

######  Proof A.5.

Let $\epsilon>0$. We show that $S$ is “$\epsilon$-robust-reachable”. That is,
$M^{n}x+\epsilon M^{n}\mathcal{B}$ intersects $S$ for some $n$. Consider
$\mathcal{A}_{\epsilon/2}$. By assumption, there exists $N_{1}$ such that for
all $n>N_{1}$, $\mathcal{A}_{\epsilon/2}(n)$ intersects $S$. Let
$\epsilon^{\prime}$ be sufficiently small such that for all $z$

$||\Gamma^{n}-z||<\epsilon^{\prime}\implies\exists\Delta\in\frac{\epsilon}{2}\mathcal{B}:\,f(n,z)x=M^{n}x+M^{n}\Delta.$

Consider the limiting shape $L$ for the sequence

$T_{n}=\\{z\in\mathcal{T}:\mathcal{A}_{\epsilon/2}(n)(z)\textrm{ intersects
}S\\}.$

By 3.6 (b), there exists $N>N_{1}$ such that for all $n>N$,
$p+B({\mathbf{0}},\epsilon^{\prime}/2)$ intersects $T_{n}$. That is, for all
$n>N$ there exists $p_{n}\in\mathcal{T}$ such that
$||p-p_{n}||<\epsilon^{\prime}/2$ and $p_{n}\in T_{n}$. Equivalently,

$||p-p_{n}||<\epsilon^{\prime}/2\textrm{ and
}\mathcal{A}_{\epsilon/2}(n)(p_{n})\textrm{ intersects }S.$

By Kronecker’s theorem there must exist $m>N$ such that
$||\Gamma^{m}-p||<\epsilon^{\prime}/2$. Hence we have

$||\Gamma^{m}-p_{m}||\leq\epsilon^{\prime}\textrm{ and
}\mathcal{A}_{\epsilon/2}(m)(p_{m})\textrm{ intersects }S.$

By the construction of $\epsilon^{\prime}$ there exists
$\Delta\in\frac{\epsilon}{2}\mathcal{B}$ such that
$f(n,p_{m})x=M^{n}x+M^{n}\Delta$. Hence

$M^{n}x+\epsilon
M^{n}\mathcal{B}=M^{n}x+\frac{\epsilon}{2}M^{n}\mathcal{B}+\frac{\epsilon}{2}M^{n}\mathcal{B}\supseteq
f(n,p_{m})x+\frac{\epsilon}{2}\mathcal{B}=\mathcal{A}_{\epsilon/2}(m)(p_{m}).$

Since $\mathcal{A}_{\epsilon/2}(m)(p_{m})$ intersects $S$, it follows that
$M^{n}x+\epsilon M^{n}\mathcal{B}$ intersects $S$ too.

##  Appendix B Continuous-time robust reachability problem

In this section, we take the continuous robust reachability problem for linear
dynamical systems and show that it can be reduced into the bounded-time
reachability problem for semialgebraic target sets. The techniques we use are
very similar to the discrete setting. The only major difference is that
deciding the continuous-time robust reachability problem, requires Schanuel’s
conjecture.

Let $M\in(\mathbb{R}\cap{\overline{\mathbb{Q}}})^{L\times L}$ be a matrix in
real JNF, $x\in\mathbb{Q}^{L}$ be a starting point, and
$S\subseteq\mathbb{R}^{L}$ be a semialgebraic target set. We want to show how
to decide whether $\forall\epsilon>0.\,\exists t\in\mathbb{R}_{\geq
0},\delta\in B(\boldsymbol{0},\epsilon)\colon e^{Mt}(x+\delta)\in S$.

Let $\mathcal{B}$ be the control set as defined for the discrete setting. This
gives $\mathcal{B}(t)=e^{Mt}\mathcal{B}$ and the $\epsilon$-pseudo-orbit of
the continuous system at time $t\in\mathbb{R}_{\geq 0}$ can be defined as
${\widetilde{\mathcal{O}}}_{\epsilon}(t)=e^{Mt}x+\mathcal{B}(t)$. We can state
the continuous robust reachability Problem as

$\forall\epsilon>0.\;\exists t\in\mathbb{R}_{\geq
0}\colon{\widetilde{\mathcal{O}}}_{\epsilon}(t)\cap S\neq\emptyset$

One can define an abstraction for $e^{Mt}x$ similar to the discrete case. In
particular, for $\alpha\in\mathbb{R}\cap{\overline{\mathbb{Q}}}$ let
$R(\alpha)=\begin{bmatrix}\cos(\alpha)&-\sin(\alpha)\\\
\sin(\alpha)&\cos(\alpha)\end{bmatrix}$ and for $1\leq i\leq k$ let
$\gamma_{i}=\operatorname{Im}(\lambda_{i})$ and
$r_{i}=\operatorname{Re}(\lambda_{i})$ for a non-real eigenvalue $\lambda_{i}$
of the block $J_{i}$. Finally, let $f:\mathbb{R}_{\geq
0}\times\mathbb{R}^{k}\to\mathbb{R}^{L\times L}$ be the “matrix builder”
function, defined as follows.

$f(t,(\alpha_{1},\ldots,\alpha_{k}))=\operatorname{diag}(g(\alpha_{1}),\ldots,g(\alpha_{k}),e^{J_{k+1}t},\ldots,e^{J_{d}t})$

where

$g(\alpha_{i})=\begin{bmatrix}A_{i}&tA_{i}&\cdots&\frac{t^{\sigma_{i}-1}}{(\sigma_{i}-1)!}A_{i}\\\
&A_{i}&\ddots&\vdots\\\ &&\ddots&tA_{i}\\\ &&&A_{i}\end{bmatrix}\textrm{ and
}A_{i}=e^{r_{i}t}R(\alpha).$

Let

$\mathcal{T}=\\{(R(\gamma_{1}t),\ldots,R(\gamma_{k}t)):t\in\mathbb{R}_{\geq
0}\\}.$

The set $\mathcal{T}$ is semialgebraic and effectively computable. Further
define

$\mathcal{A}_{\epsilon}(t)(z)=f(t,z)x+\epsilon\mathcal{B}(t)\textrm{ and
}\mathcal{A}_{\epsilon}(t)=\\{\mathcal{A}_{\epsilon}(t)(z):z\in\mathcal{T}\\}.$

Notice that we have
$\mathcal{A}_{\epsilon}(n)\supseteq{\widetilde{\mathcal{O}}}_{\epsilon}(n)$.
The next lemma shows that if $z$ is picked close enough to
$\Gamma(t)=(\gamma_{1}t,\ldots,\gamma_{k}t)$, then $e^{Mt}x$ can be
approximated by $f(t,z)x$.

######  Lemma B.1.

Given $z=(\alpha_{1},\ldots,\alpha_{k})$, a time point $t\in\mathbb{R}_{\geq
0}$, an update matrix $M$ and a starting point $x$,

$f(t,(\alpha_{1},\ldots,\alpha_{k}))x=e^{Mt}x+e^{Mt}\Delta$

has a solution

$\Delta=(\Delta_{1},\ldots,\Delta_{k},{\mathbf{0}},\ldots,{\mathbf{0}})$

where $\Delta_{i}(j)=R(-\gamma_{i}t)(R(\alpha_{i})-R(\gamma_{i}t))x_{i}(j)$
for $1\leq i\leq k$ and $1\leq j\leq\sigma_{i}$.

We have the following corollary, similar to the discrete setting.

######  Corollary B.2.

Given $M$ and $x$, there exists $C$ such that for all $\epsilon>0$ and
$z\in(\mathbb{R}\cap{\overline{\mathbb{Q}}})^{k}$,

$||\Gamma(t)-z||<C\epsilon\implies\exists\Delta\in\epsilon\mathcal{B}:\,f(t,z)x=e^{Mt}x+e^{Mt}\Delta.$

Before stating the main result of this section, we state the dichotomy lemma
for the continuous-time setting.

######  Lemma B.3.

Either

  1. 1.

for every $\epsilon>0$ there exists $T_{\epsilon}$ such that for all
$t>T_{\epsilon}$, $\mathcal{A}_{\epsilon}^{c}(t)$ intersects $S$, or

  2. 2.

there exist computable $T$ and $\epsilon>0$ such that
$\mathcal{A}_{\epsilon}^{c}(t)$ does not intersect $S$ for all $t>T$.

Moreover, it can be effectively determined which case holds.

We first consider Case 1 and show that if this case holds, the answer to the
robust reachability problem is positive. The proof would be exactly the same
as for the discrete setting.

######  Lemma B.4.

If for all $\epsilon>0$ there exists $T_{\epsilon}\in\mathbb{R}_{\geq 0}$ such
that for all $t>T_{\epsilon}$, $\mathcal{A}_{\epsilon}(t)$ intersects $S$,
then $S$ is robust reachable.

Similar to the pseudo-reachability problem, we know that given a finite-time
interval, to answer bounded-time robust reachability questions, it is enough
to check whether the given target set is reachable within the specified time
interval or not. Now, we are ready to state the main result of this section.

######  Lemma B.5.

The continuous robust reachability problem for linear dynamics reduces to
bounded-time reachability problem for linear continuous-time systems.

######  Proof B.6.

Using the results of Lemma B.3, we can effectively decide whether Case 1 holds
or not. If Case 1 holds, by Lemma B.4, we know that $S$ is robustly reachable.
Otherwise, Case 2 holds and we effectively compute the time-bound $T$ and
therefore, need to check if $S$ is reachable by the orbit of the system within
the time interval $[0,T]$. Therefore, the robust reachability problem reduces
into the bounded-time reachability problem for continuous-time linear
dynamical systems.

Finally, since the bounded-time reachability problem for continuous-time
linear dynamical systems can be encoded in
$\mathbb{R}_{\exp,\cos{\upharpoonright}[0,T]}$, we have the following
(conditional) decidability result.

######  Corollary B.7.

The continuous robust reachability problem for the continuous-time linear
dynamical systems is decidable subject to Schanuel’s conjecture.