text:
\section{Additional preliminaries}\label{apx:prelim}

\subsection{Jordan decomposition and matrix exponential}

Given a square matrix $A$ of order $n$ with rational entries,
one can find matrices $P$ and $\Lambda$ (possibly with complex algebraic entries)
such that $A = P \Lambda P^{-1}$.
Here $\Lambda$ is a block diagonal matrix $\diag(J_1,J_2,\dots,J_m)$ where
the $J_i$ are matrices of a special form (given below) known as the Jordan blocks.
A particular application of Jordan decomposition is to compute the exponential of a matrix.
From the above definition, it is clear that if $A = P \Lambda P^{-1}$, then $e^{At} = P e^{\Lambda t} P^{-1}$.
If $\Lambda = \diag(J_1,J_2,\ldots,J_m)$, then it is not hard to see that $e^{\Lambda t} = \diag(e^{J_1 t},e^{J_2 t},\ldots,e^{J_m t})$.
A closed form expression for a Jordan block $e^{J_i t}$ is given by
\[
    e^{J_i t} = e^{\lambda_i t}\begin{bmatrix}
    1 & t & \frac{t^2}{2} & \cdots & \frac{t^{k-1}}{(k-1)!} \\
    0 & 1 & t & \cdots & \frac{t^{k-2}}{(k-2)!} \\
    \vdots & \vdots & \ddots & \ddots & \vdots \\
    0 & 0 & \cdots & 1 & t \\
    0 & 0 & \cdots & 0 & 1
    \end{bmatrix},

    J_i = \begin{bmatrix}
        \lambda_i & 1 & 0 & \cdots & 0 \\
        0 & \lambda_i & 1 & \cdots & 0 \\
        \vdots & \vdots & \ddots & \ddots & \vdots \\
        0 & 0 & \cdots & \lambda_i & 1 \\
        0 & 0 & \cdots & 0 & \lambda_i
        \end{bmatrix}
\]
where $\lambda_i$ is an eigenvalues of $A$ and $k$ is the size of the Jordan block. A consequence
of this normal form is the \emph{real Jordan normal form}: if $A$ is real then its Jordan form
can be nonreal. However, one can allow more general blocks to recover a real representation: a real
Jordan block is either a complex Jordan block with a real $\lambda_i$, or a block matrix of the form
\[
    J_i'=\begin{bmatrix}C_i&I_2&0&\cdots&0\\0&C_i&I_2&\cdots 0\\\vdots&\vdots&\ddots&\ddots&\vdots\\
            0&0&\cdots&C_i&I_2\\0&0&\cdots&0&C_i\end{bmatrix}
    \qquad\text{where}\qquad
    C_i=\begin{bmatrix}a_i&-b_i\\b_i&a_i\end{bmatrix}
\]
where $\lambda_i=a_i+ib_i$. In this case, one can ensure that the transformation matrix $P$ is also real.
This form is particularly useful for simple blocks since the exponential of $C_i$ is a scaling-and-rotate
matrix:
\[
    e^{C_it}=e^{a_it}\begin{bmatrix}\cos(b_it)&\sin(b_it)\\-\sin(b_it)&\cos(b_it)\end{bmatrix}.
\]

\section{Proof of Lemma~\ref{prop:reduce_controllable_minkowski}}\label{apx:reduce_controllable_minkowski}

Following the observations of \Cref{sec:control_theory} and in particular \eqref{eq:decompose_C_hypercube},
we have that $\Reach_\tau(A,B,[-1,1]^m)=\sum_{i=1}^m\Reach_\tau(A,b_i,[-1,1])$. We now focus on the case
where $B=b$ is a column vector. If $(A,b)$ is controllable then there is nothing to do. Otherwise
let $V=\Span(b,Ab,\ldots,A^{n-1}b)$, and assume that $k:=\dim V<n$.
Then $b\in V$ and $AV\subseteq V$, so by a change of basis $P$ sending $V$ to $\RR^k$ we have
\[
    P^{-1}AP=\begin{bmatrix}A_V&0\\0&*\end{bmatrix},\qquad
    P^{-1}b=\begin{bmatrix}b_V\\0\end{bmatrix}.
\]
Then $\Span(b_V,A_Vb_V,\ldots,A_V^{k-1}b_V)=\RR^k$ by construction, therefore $(A_V,b_V)$ is controllable.
Furthermore, it is clear that the spectrum of $A_V$ is included in that of $A$.
On the other hand, for any input $u$,
\begin{align*}
    \int_0^\tau e^{At}bu(t)\dd t
        &=P\int_0^\tau \begin{bmatrix}e^{A_Vt}&*\\0&*\end{bmatrix}\begin{bmatrix}b_V\\0\end{bmatrix}u(t)\dd t\\
        &=P\begin{bmatrix}
            \int_0^\tau e^{A_Vt}b_Vu(t)\dd t\\0
        \end{bmatrix}.
\end{align*}
It follows that
\[
    \Reach_\tau(A,b,[-1,1])=PJ_k\Reach(A_V,b_V,[-1,1])
    \quad\text{where}\quad
    J_k=\begin{bmatrix}I_k\\0\end{bmatrix}\in\RR^{n\times k}.
\]
Going back to the general case, we now have that
\[
    \Reach_\tau(A,B,[-1,1]^m)=\sum_{i=1}^mP_i\Reach_\tau(C_i,b_i,[-1,1]).
\]
Assume there are formulas $\Phi_1,\ldots,\Phi_m$ in some theory $\RRtheory$
to expressible membership in $\Reach_\tau(C_i,b_i,[-1,1])$. Then we can express membership of some $y\in\RR^n$
in $\Reach_\tau(A,B,[-1,1]^m)$ by the formula
\[
    \Phi(y):=\exists z_1,\ldots,\exists z_k.\,\Phi_1(z_1)\wedge\cdots\wedge\Phi_m(z_m)\wedge y=P_1z_1+\cdots+P_mz_m.
\]
Clearly if the theory $\RRtheory$ contains $\RRtarski$ then $\Phi$ is in $\RRtheory$. If instead of a
formula $\Phi_i$ for $\Reach_\tau(C_i,b_i,[-1,1])$, we have a formula for its boundary $\partial\Reach_\tau(C_i,b_i,[-1,1])$,
then we note that $\Reach_\tau(C_i,b_i,[-1,1])$ is open convex by \Cref{prop:null_controllable_region_desc}
when $\tau=\infty$ and convex closed when $\tau<\infty$,
hence we can write a formula for $\Reach(C_i,b_i,[-1,1])$ from $\Phi_i$, as shown below.

Let $C\subseteq\RR^n$ be an open (resp. closed) bounded convex set, if we have a formula $\Phi$ to express
membership in $\partial C$ in some theory $\RRtheory$ that subsumes $\RRtarski$, then we can write
a formula in $\RRtheory$ to express membership in $C$.
Indeed, by Krein–Milman theorem, the closure $\overline{C}$ of $C$ is the convex hull of its extreme points,
but the extreme points of $\overline{C}$ are on the boundary $\partial C$. Hence $\overline{C}$
is the convex hull of $\partial C$. It follows by Carathéodory's theorem that any point in $\overline{C}$
is the convex combination of at most $n+1$ in $\partial C$. Hence we can write a formula $\psi$ to
decide membership in $\overline{C}$. If $C$ is closed then $C=\overline{C}$ so we are done.
If $C$ is open, we know that $C=\overline{C}\setminus\partial C$,
hence we can write a formula for $C$.

\section{Proof of Proposition~\ref{prop:complement_border_reach_lti_approx}}\label{apx:complement_border_reach_lti_approx}

We first observe that we can reduce to the case where $B=b$ is a column vector and $(A,b)$
is controllable. Indeed, apply \Cref{prop:reduce_controllable_minkowski} to get computable $C_1,\ldots,C_k$
and $P_1,\ldots,P_k$ such that
\[
    \Reach(A,B,[-1,1]^m)=\sum_{i=1}^mP_i\Reach(C_i,b_i,[-1,1]).
\]
Now assume that we have some convex under/over-approximation $Q_i^-,Q_i^+$ of
$\Reach(C_i,b_i,[-1,1])$ for all $i$. Then $\sum_{i=1}^mP_iQ_i^\pm$ is a convex under/over-approximation
by the property of the Minkowski sum of convex sets, furthermore this sum can be computed effectively.
Note that in this reduction, the matrix $A$ has not changed, hence it is still stable.

We now focus on the case where $B=b$ is a column vector such that $(A,b)$ is controllable.
We can apply \Cref{thm:bdry_descrptn} to get that $\Control(A,b,U)$ is an open convex set
containing $\boldsymbol{0}$ and
\[
    \partial\Reach(A,b,U) = \set*{\int_0^{\infty} e^{A t}b\sgn(c^Te^{A t}b)\dd t: c \in \RR^n\setminus \{\mathbf{0}\}}.
\]
Observe that only the direction of $c$ matters so we can restrict the set to the \emph{compact}
subset of $c$ such that $\twonorm{c}=1$.
Let $f_c(t)=e^{A t}b\sgn(c^Te^{A t}b)$ and observe that since $A$ is stable,
$f_c(t)\to0$ as $t\to\infty$. In fact, one can compute constants $D$ and $\alpha<0$ such that
$\|f_c(t)\|\leqslant De^{\alpha t}$ for all $t\geqslant0$.
Let $T$ to be fixed later,
then
\[
    \left\|\int_{0}^\infty f_c(t)\dd t-\int_0^Tf_c(t)\dd t\right\|\leqslant
        \int_T^\infty De^{\alpha t}\dd t=D\alpha^{-1}e^{\alpha T}.
\]
Furthermore, one can approximate $\int_0^Tf_c(t)\dd t$ with arbitrary precision given $T$ and $c$,
by using the fact that $c^Te^{At}b$ is analytical and computable. Furthermore, $c\mapsto \int_0^Tf_c(t)\dd t$
is continuous since the zero-crossings of $c^Te^{At}B$ move continuously with $c$ and the
(discontinous) tangential zeros that can appear do not change the integral. It follows that
on the compact set $\set{c:\twonorm{c}=1}$, it has bounded variations, with a computable bound.
Putting everything together, this allows us to sample the border with sufficiently many points
as to obtain an underapproximation and overapproximation of the border, in the form of a convex set.

\section{Proof of Proposition~\ref{prop:decide_real_eigen_rexp}}\label{apx:decide_real_eigen_rexp}

By putting $A$ in Jordan Normal Form, write $A=Q^{-1}MQ$ where $Q$ is invertible
and $M$ is made of Jordan blocks. Since $A$ has real spectrum, $Q$ and $M$ are real matrices
and $\Reach(A,B,U)=Q^{-1}\Reach(M,QB,U)$, we can now assume that $A$ only consists of Jordan blocks
since $y\in\Reach(A,B,U)$ if and only if $Qy\in\Reach(M,QB,U)$.

Assume that $A=\diag(J_1,\ldots,J_k)$ consist of Jordan blocks. Without loss of generality, we can assume that
the blocks are ordered by increasing eigenvalue. Hence we can write $A=\diag(A_1,A_2)$ where $A_1$
contains the nonnegative $\lambda_i$ and $A_2$ the negative ones. Then $A_1$ is weakly-antistable and
$A_2$ is stable. Decompose $B$ into $B_1$ and $B_2$ accordingly. Then by \Cref{prop:null_controllable_region_desc},
$\Reach(A,B,U)=\RR^{n_1}\times \Reach(A_2,B_2,U)$. We can then apply \Cref{prop:reduce_controllable_minkowski}
to decompose $\Reach(A_2,B_2,U)$ into smaller controllable problems $(C_i,b_i)$, where each $C_i$
also has a real spectrum. It then suffices to show that membership in $\partial\Reach(C_i,b_i,[-1,1])$
is expressible in $\RRexp$ for each subproblem to conclude by \Cref{prop:reduce_controllable_minkowski}.

Assume that $A$ only has negative eigenvalues, $B=b$ is a column vector, $(A,b)$ is controllable and $U=[-1,1]$.
Then by \Cref{thm:bdry_descrptn} we have that
$\partial\Reach(A,b,[-1,1]) = \set*{\beta_c: c \in \RR^n\setminus \{\mathbf{0}\}}$, where
\[
    \beta_c:=\int_0^{\infty}e^{At}b\sgn(c^Te^{A t}b)\dd t
\]
But observe that $f_c(t):=c^Te^{A t}b$ is an exponential polynomial in $t$. Furthermore,
it has at most $n-1$ zeros by \Cref{lem:control_fc} since $A$ has real eigenvalues and $b,c$
are nonzero. Let $0\leqslant k\leqslant n-1$ and assume that $f_c$ has $k$ nontangential zeros
(the tangential zeros will play no role) $0<t_1<\cdots<t_k$. Then, depending
on the sign of $f_c(0)$, and noting that the sign of $f_c$ changes at each $t_i$, we have
that
\begin{align*}
    \beta_c
        &=\pm\left(\int_0^{t_1}e^{-At}b\dd t+\sum_{i=1}^{k-1}\int_{t_i}^{t_{i+1}}(-1)^i\dd t
            +(-1)^k\int_{t_k}^{\infty}e^{-At}b\dd t\right)\\
        &=\pm A^{-1}\left(I_n+2\sum_{i=1}^k(-1)^ie^{At_i}\right)b\\
        &=\pm R_k(t_1,\ldots,t_k)
\end{align*}
which is also a (vector of) exponential polynomials. We can now
write a formula in $\RRexp$ to express that a target $y$ is on the border:
\begin{align*}
    \Phi(y)
        &:=\exists c.c\neq0\bigwedge\bigvee_{k=0}^d\Phi_k(y,c)
    \intertext{to check for a point on a border in direction $c$,}
    \Phi_k(y,c)
        &:=\exists t_1,\ldots,t_k.\Psi_k(c,t)\bigwedge\Psi_k'(c,t)\bigwedge
            \bigwedge_{j=1}^n\left(y_j=R_{k,j}(t)\right)
    \intertext{to match the target with some parameters $z_1,\ldots,z_k$,}
    \Psi_k(c,t)
        &:=\bigwedge_{i=1}^k \left(f_c(t_i)=0\wedge f_c'(t_i)\neq 0\right)
            \bigwedge 0<t_1<\cdots<t_k
    \intertext{to check that the $t_i$ are zeros of $Q(c,\cdot)$,}
    \Psi_k'(c,t)
        &:=\forall u.(u>0\wedge f_c(u)=0\wedge f_c'(u)\neq 0)\Rightarrow\bigvee_{i=1}^k u=z_i
    \intertext{to check the $t_i$ are the only zeros of $Q(c,\cdot)$.}
\end{align*}
We note that those are indeed formulas in $\RRexp$ because $f_c,f_c'$ and $e^{At}$ are exponential
polynomials in $t$ and $c$ and they can be computed by putting $A$ in Jordan normal form, and all
those exponential polynomials have algebraic coefficients since $b$ and $A$ have algebraic coefficients.
This shows that deciding the border reduces to deciding a formula in $\RRexp$.

\section{Proof of Proposition~\ref{prop:decide_complex_eigen_2d_rexpsin}}\label{apx:decide_complex_eigen_2d_rexpsin}

If $A$ has real eigenvalues, then the decidability reduces to $\RRexp$ by \Cref{prop:decide_real_eigen_rexp},
which is decidable in $\RRexpsin$. Otherwise, since $A$ is real, it must have two conjugate complex
but nonreal eigenvalues. Hence, we can put $A$ in \emph{real} Jordan Form: $A=P^{-1}JP$ where $P$
is real and
\[
    J=\begin{bmatrix}\lambda&\theta\\-\theta&\lambda\end{bmatrix},\qquad
\]
where $\lambda,\theta\in\RR$. It follows that $\Reach(A,B,U)=P^{-1}\Reach(J,PB,U)$
so we now focus on this particular case.
Assume that $A$ is a real Jordan block of the form above. Then
\[
    e^{Jt}=e^{\lambda t}\begin{bmatrix}\cos(\theta t)&\sin(\theta t)\\-\sin(\theta t)&\cos(\theta t)\end{bmatrix}.
\]
Furthermore, we can decompose $B$ into columns vectors $b_1,\ldots,b_m$ so that
\[
    \Reach(A,B,[-1,1]^m)=\Reach(A,b_1,[-1,1])+\cdots+\Reach(A,b_m,[-1,1])
\]
so we now assume that $B=b$ is a column vector. We further reduce to the case where $b$ has
norm $1$ by noticing that $\Reach(A,b_1,[-1,1])=\twonorm{b}\Reach(A,b/\twonorm{b},[-1,1])$.
Now $(A,b)$ is controllable (unless $b=0$ which is trivial)
since $A$ rotates (and rescale) $b$ by an angle $\theta$ and $\theta\neq 0\pmod \pi$ (indeed,
$\theta$ is nonzero and algebraic). Hence we can apply \Cref{prop:null_controllable_region_desc}
and \Cref{thm:bdry_descrptn} to get that either $\Reach(A,b,[-1,1])=\RR^2$ if $\lambda>0$, or
$\partial\Reach(A,B,[-1,1]^m)=\set{\beta_c:c\in\RR^2\setminus\set{0}}$ where
\[
    \beta_c:=\int_0^{\infty}e^{At}b\sgn(c^Te^{A t}b)\dd t.
\]
We now focus on this case since the other one is trivial. Since the dimension is two, we can write
$c_\phi:=\begin{bmatrix}\cos(\phi)&\sin(\phi)\end{bmatrix}^T$ for $\phi\in[0,2\pi)$ and
$b=\begin{bmatrix}\cos\beta&\sin\beta\end{bmatrix}^T$.
Then,
\[
    \begin{bmatrix}\cos(\theta t)&\sin(\theta t)\\-\sin(\theta t)&\cos(\theta t)\end{bmatrix}
        \begin{bmatrix}a\\b\end{bmatrix}
    =\begin{bmatrix}\cos(\theta t+\beta)\\\sin(\theta t+\beta\end{bmatrix}.
\]
and
\begin{align*}
    \sgn(c^Te^{A t}b)
        &=\sgn\left(\begin{bmatrix}\cos(\phi)&\sin(\phi)\end{bmatrix}
        \begin{bmatrix}\cos(\theta t+\beta)\\\sin(\theta t+\beta\end{bmatrix}\right)\\
        &=\sgn(\cos(\theta t+\beta+\phi)).
\end{align*}
Hence,
\begin{align*}
    \beta_\phi
        &:=\beta_{c_\phi}=\int_0^\infty e^{\lambda t}\begin{bmatrix}\cos(\theta t+\beta)\\\sin(\theta t+\beta\end{bmatrix}
        \sgn(\cos(\theta t+\beta+\phi))\dd t\\
        &=e^{i\beta}\int_0^te^{(\lambda+i\theta)t}\sgn(\cos((\theta t+\beta+\phi))\dd t
\end{align*}
when viewed as a complex number (to simplify computations). Let $t_{\phi}$ denote the smallest
$t\geqslant 0$ such that $\cos(\theta t+\beta+\phi)=0$ and $\varepsilon_\phi=\sgn(\cos(\beta+\phi))$,
except when $t_\phi=0$ in which case we let $\varepsilon_\phi=-1$.
Then
\begin{align*}
    \beta_\phi
        &=e^{i\beta}\varepsilon_\phi\left(\int_0^{t_\phi}e^{(\lambda+i\theta )t}\dd t
        -\sum_{k=0}^\infty\int_{t_\phi+k\tfrac{\pi}{\theta}}^{t_\phi+(k+1)\tfrac{\pi}{\theta}}
        (-1)^ke^{(\lambda+i\theta )t}
        \dd t\right)\\
        &=\frac{e^{i\beta}\varepsilon_\phi}{\lambda+i\theta}\Big(e^{(\lambda+i\theta )t_\phi}-1\\
        &\hspace{1.5cm}-\sum_{k=0}^\infty(-1)^k\left(e^{(\lambda+i\theta )(t_\phi+(k+1)\tfrac{\pi}{\theta})}
        -e^{(\lambda+i\theta )(t_\phi+(k+1)\tfrac{\pi}{\theta})}\Big)
        \right)\\
        &=\frac{e^{i\beta}\varepsilon_\phi}{\lambda+i\theta}\left(-1+
        2\sum_{k=0}^\infty(-1)^ke^{(\lambda+i\theta )(t_\phi+k\tfrac{\pi}{\theta})}
        \right)\\
        &=\frac{e^{i\beta}\varepsilon_\phi}{\lambda+i\theta}\left(-1+
        2e^{(\lambda+i\theta)t_\phi}\sum_{k=0}^\infty(-1)^ke^{k(\lambda+i\theta )\tfrac{\pi}{\theta}}
        \right)\\
        &=\frac{e^{i\beta}\varepsilon_\phi}{\lambda+i\theta}\left(-1+
        2e^{(\lambda+i\theta)t_\phi}\frac{1}{1+e^{(\lambda+i\theta)\tfrac{\pi}{\theta}}}\right)\\
        &=\frac{e^{i\beta}\varepsilon_\phi}{\lambda+i\theta}\left(-1+
        2e^{(\lambda+i\theta)t_\phi}\frac{1}{1-e^{\tfrac{\lambda\pi}{\theta}}}\right).
\end{align*}
One can then obtain an expression for each coordinate of $\beta_\phi$ viewed as a 2D vector.
In particular, this expression is expressible in $\RRexpsin$ where $\sin$ is taken over some
bounded interval. Indeed, $\lambda,\beta$ and $\theta$ are algebraic, $t_\phi$ can be express in with an equation
involving a bounded $\sin$ since we have the trivial bound $t_\phi\leqslant \tfrac{2\pi}{\theta}$.
We can then express $e^{(\lambda+i\theta)t_\phi}$ using a combination of exponential and bounded $\sin$,
again noting that $\theta t_\phi\leqslant 2\pi$. We can also express $\pi$ using an equation on
bounded $\sin$ ($\sin{\pi}=0 \wedge (\forall y.\,0<y<\pi \implies \sin{y}\neq 0)$) hence we can define
$e^{\tfrac{\lambda\pi}{\theta}}$. It follows that we can express $\beta_\phi$ and hence the boundary
in $\RRexpsin$. We then conclude using \Cref{prop:reduce_controllable_minkowski}.

\section{Proof of Proposition~\ref{prop:decide_2d_real_eigen}}\label{apx:decide_2d_real_eigen}

If $A$ is diagonalizable, and since it has real eigenvalues, we can write $A=P^{-1}DP$ where $P$ is real and $D$ is real diagonal.
Then $\Reach(A,B,U)=P^{-1}\Reach(D,PB,U)$ so we only need to decide if $Py\in\Reach(D,PB,U)$.
But in dimension $2$ all columns of $PB$ necessarily have at most two nonzero entries
so we can conclude using \Cref{prop:decide_real_mat_uncond}.
Otherwise, $A$ only has one eigenvalue, which is real, so we conclude with \Cref{prop:decide_real_mat_uncond}.

\section{Proof of Proposition~\ref{prop:decide_bounded_time_rexpsin}}\label{apx:decide_bounded_time_rexpsin}

Recall that we are concerned with a time-bounded problem, for some time bound $\tau<\infty$
that is algebraic.
Since $U=[-1,1]^m$, we can apply \Cref{prop:reduce_controllable_minkowski} to
to decompose $\Reach(A,B,U)$ into smaller controllable problems $(C_i,b_i)$, where each $C_i$
is still a real matrix. It then suffices to show that membership in $\partial\Reach(C_i,b_i,[-1,1])$
is expressible in $\RRexpsin$ for each subproblem to conclude by \Cref{prop:reduce_controllable_minkowski}.

Now consider the case where $B=b$ is a column vector and $(A,b)$ is controllable and $U=[-1,1]$.
Since $U$ is convex closed and $\tau$ is finite, it is clear that $\Reach$ is convex closed.
A simple proof similar to that of \Cref{thm:bdry_descrptn} shows that
$\partial\Reach_\tau(A,B,U)=\set*{\beta_c: c \in \RR^n\setminus \{\mathbf{0}\}}$, where
\[
    \beta_c:=\int_0^{\tau}e^{At}b\sgn(c^Te^{A t}b)\dd t
\]
Indeed, observe that for any $c\in\RR^n\setminus \{\mathbf{0}\}$,
\begin{align*}
    c^T\int_0^{\tau} e^{A t}b\sgn(c^Te^{A t}b)\dd t
        &=\int_0^{\tau} c^Te^{A t}b\sgn(c^Te^{A t}b)\dd t\\
        &=\int_0^{\tau} |c^Te^{A t}b|\dd t
\end{align*}
and for any $u:[0,\tau]\to[-1,1]$ measurable,
\begin{align*}
    c^T\int_0^\tau e^{A t}bu(t)\dd t
        &=\int_0^\tau c^Te^{A t}bu(t)\dd t\\
        &\leqslant\int_0^\tau |c^Te^{A t}bu(t)|\dd t
        \leqslant\int_0^\tau |c^Te^{A t}b|\dd t.
\end{align*}
Hence, $\int_0^{\tau} e^{A t}b\sgn(c^Te^{A t}b)\dd t$ is a maximizer in direction $c$ and we conclude
by standard results about convex sets. But observe that $f_c(t):=c^Te^{-A t}b$ is an exponential polynomial in $t$.
Furthermore, it has a bounded number of zeroes by \Cref{lem:control_fc} since $b,c$ are nonzero.
We can even obtain an explicit formula for this bound by induction on the number of terms, or invoke
a more general result on zeroes in a complex ball by Tijdeman \cite{TIJDEMAN19711}:

\begin{lemma}
    If $f(z) = \sum_{k=1}^l P_k(z)e^{\lambda_k z}$ where $P_k$ is a polynomial of degree $\rho_k-1$,
    the number of zeros in the complex plane in any ball of radius $R$ is bounded by $3(n_0-1)+4R\Delta$
    where $n_0 = \sum_{k=1}^l \rho_k$ and $\Delta = max_{k} |\lambda_k|$. \\
\end{lemma}

In our case, the bound $N$ on the number of zeroes is clearly computable from $A$. Let $c\neq\mathbf{0}$,
$0\leqslant k\leqslant N$ and assume that $f_c$ has $k$ nontangeantial zeros
(the tangeantial zeros will play no role) $0<t_1<\cdots<t_k$ in $[0,\tau]$. Then, depending
on the sign of $f_c(0)$, and noting that the sign of $f_c$ changes at each $t_i$, we have that
\begin{align*}
    \beta_c
        &=\pm\left(\int_0^{t_1}e^{-At}b\dd t+\sum_{i=1}^{k-1}\int_{t_i}^{t_{i+1}}(-1)^i\dd t
            +(-1)^k\int_{t_k}^{\tau}e^{-At}b\dd t\right)\\
        &=\pm A^{-1}\left(I_n+2\sum_{i=1}^k(-1)^ie^{At_i}-(-1)^ke^{-A\tau}\right)b\\
        &=\pm R_k(t_1,\ldots,t_k)
\end{align*}
which is also a (vector of) exponential polynomials. We can now proceed as in the proof of \Cref{prop:decide_real_eigen_rexp}
and write a formula in $\RRexpsin$ to express that a target $y$ is on the border. The crucial
point is that the exponentials in $e^{At_i}$ will not only involve the real exponential but also
some sine and cosine. This is where the boundedness is crucial: since $t_i\leqslant\tau$, we only
need bounded sine and cosine in our formulas. Also note that since $\tau$ is algebraic, we can
write $\tau$ in the formulas (this is necessary to express $e^{-A\tau}$); we note that since we are
working in $\RRexpsin$, we could in fact allow more general $\tau$ than just algebraic numbers.
This shows that deciding the border reduces to deciding a formula in $\RRexpsin$.

\section{Proof of Theorem~\ref{th:lti_hard_skolem}}\label{apx:lti_hard_skolem}

Let $c,A,b$ be an instance of the Continuous Skolen problem. Let $f(t)=c^Te^{At}b$,
the problem asks whether $f$ has any zero at $t\geqslant 0$. Without loss of generality,
we can assume that $c^Tb\geqslant0$ by changing $b$ into $-b$.

Now let $u=(1,\ldots,1)$, $B\in\QQ^{n\times n}$ be such that $Bu=b$ and $U=\set{u}$, and observe that by definition,
\[
    \Reach(A,AB,U)
        =\set*{\int_0^Te^{At}ABu\dd t:T\geqslant 0}
        =\set*{(e^{At}-I_n)b:t\geqslant 0}.
\]
But notice that for any $t\geqslant 0$,
\[
    c^T(e^{At}-I_n)b
        =c^Te^{At}b-c^Tb
        =f(t)-c^Tb.
\]
Hence if we define the set $Y=\set{x\in\RR^n:c^Tx\leqslant -c^Tb}$, which is a hyperplane, then
$Y$ is reachable if and only if there exists $t\in\RR^n$ such that $f(t)\leqslant 0$.
But since $f(0)=c^Tb\geqslant 0$ by assumption, this last condition is equivalent to the existence
of a zero by continuity. This shows that Skolem instance $(c,A,b)$ is positive if and only the
Set Reachability instance $(A,AB,U,Y)$ is positive.

Note that we can easily modify the instance to further strengthen the result like in the proof
of \Cref{th:lti_nontangen_hard_skolem}. More precisely, we can ensure that the LTI instance is
stable and that the set $Y$ is compact convex.

\section{Details on Figure~\ref{fig:ex_reach2d}}\label{sec:details_fig_reach}

Since all eigenvalues of $A$ are negative, it is stable. Furthermore, one checks that $b_1$ and $Ab_1$
are linearly independent, hence $(A,b_1)$ is controllable. We can apply \Cref{thm:bdry_descrptn}
to get the description of the boundary:
\begin{align*}
    \partial\Reach(A,b_1)
        &=\set*{\int_0^{\infty} e^{A t}b\sgn(c^Te^{A t}b)\dd t: c \in \RR^2\setminus \{\mathbf{0}\}}\\
        &=\Bigg\{\int_0^{\infty} \begin{bmatrix}e^{-\frac{t}{2}}&0\\0&e^{-\tfrac{t}{3}}\end{bmatrix}
            \begin{bmatrix}1\\1\end{bmatrix}\times\\
        &\hspace{0.5cm}\sgn\left(\begin{bmatrix}c_1&c_2\end{bmatrix}\begin{bmatrix}e^{-\frac{t}{2}}&0\\0&e^{-\tfrac{t}{3}}\end{bmatrix}
            \begin{bmatrix}1\\1\end{bmatrix}\right)\dd t: c_1,c_2 \in \RR\setminus \{0\}\Bigg\}\\
        &=\set*{\int_0^{\infty}\begin{bmatrix}e^{-\tfrac{t}{2}}\\e^{-\tfrac{t}{3}}\end{bmatrix}
            \sgn\left(c_1e^{-\tfrac{t}{2}}+c_2e^{-\tfrac{t}{3}}\right)\dd t: c_1,c_2 \in \RR\setminus \{0\}}.
\end{align*}
Given $c_1,c_2$ nonzero, observe that
\[
    c_1e^{-\tfrac{t}{2}}+c_2e^{-\tfrac{t}{3}}=0
    \;\Leftrightarrow\;
    1+\tfrac{c_2}{c_1}e^{\tfrac{t}{6}}=0
    \;\Leftrightarrow\;
    t=6\ln\tfrac{-c_1}{c_2}.
\]
Since only the ratio $c_1/c_2$ is important and $c_2$ must be nonzero, we can parametrize it as
$c_2=1$ and $c_1=-\alpha$, where $\alpha\in(1,+\infty)$, so that the only possible solution becomes
$t=t_1:=6\ln \alpha\geqslant0$.
Now there are two cases:
\begin{itemize}
    \item if $c_1/c_2\geqslant -1$, then there is no solution and the integral becomes
        \[
            \int_0^{\infty}\begin{bmatrix}e^{-\tfrac{t}{2}}\\e^{-\tfrac{t}{3}}\end{bmatrix}\sgn(c_1+c_2)\dd t
                =\begin{bmatrix}2\\3\end{bmatrix}\sgn(c_1+c_2);
        \]
    \item  if $c_1/c_2\leqslant -1$, then we can split the integral into two parts (the sign must change):
        \begin{align*}
            \int_0^{t_1}&\begin{bmatrix}e^{-\tfrac{t}{2}}\\e^{-\tfrac{t}{3}}\end{bmatrix}\sgn(c_1+c_2)\dd t
                -\int_{t_1}^{\infty}\begin{bmatrix}e^{-\tfrac{t}{2}}\\e^{-\tfrac{t}{3}}\end{bmatrix}\sgn(c_1+c_2)\dd t\\
                &=\begin{bmatrix}2-4e^{-t_1/2}\\3-6e^{-t_1/3}\end{bmatrix}\sgn(c_1+c_2)\\
                &=\begin{bmatrix}2-4e^{-3\ln\alpha}\\3-6e^{-2\ln\alpha}\end{bmatrix}\sgn(c_1+c_2)\\
                &=\begin{bmatrix}2-4\alpha^{-3}\\3-6\alpha^{-2}\end{bmatrix}\sgn(c_1+c_2).
        \end{align*}
\end{itemize}
Hence the boundary of the reachable set is
\[
    \partial\Reach(A,b_1)=\set*{\pm\begin{bmatrix}2-4\alpha^{-3}\\3-6\alpha^{-2}\end{bmatrix}:\alpha\in[1,\infty)}
        \cup\set*{\pm\begin{bmatrix}2\\3\end{bmatrix}}.
\]
The second reachable set is symmetric with respect to the vertical axis, hence we obtain
\[
    \partial\Reach(A,b_2)=\set*{\pm\begin{bmatrix}2-4\alpha^{-3}\\6\alpha^{-2}-3\end{bmatrix}:\alpha\in[1,\infty)}
        \cup\set*{\pm\begin{bmatrix}2\\-3\end{bmatrix}}.
\]
In order to describe the border of $\partial\Reach(A,B)$, we consider the following
question: given a nonzero vector $\tau$, find the (unique by strict convexity) maximizer
in $\partial\Reach(A,b_1)$ in direction $\tau$:
\[
    x_\tau:=\argmax_{x\in \partial\Reach(A,b_1)}\Angle{x,\tau}.
\]
Observe that we have in fact already computed this point because the description of the border by
\Cref{thm:bdry_descrptn} is in the form of maximizers. If we write $\tau=(c_1,c_2)$
as above, then
\[
    x_\tau=\begin{cases}
        \begin{bmatrix}2+4(c_1/c_2)^{-3}\\3-6(c_1/c_2)^{-2}\end{bmatrix}\sgn(c_1+c_2)
            &\text{ if }c_1/c_2\leqslant -1\\
        \begin{bmatrix}2\\3\end{bmatrix}\sgn(c_1+c_2)&\text{ otherwise}.
        \end{cases}.
\]
A similar computation for $\partial\Reach(A,b_2)$ gives
\[
    x_\tau'=\begin{cases}
        \begin{bmatrix}2+4(c_1/c_2)^{-3}\\6(c_1/c_2)^{-2}-3\end{bmatrix}\sgn(c_1-c_2)
            &\text{ if }c_1/c_2\geqslant 1\\
        \begin{bmatrix}2\\-3\end{bmatrix}\sgn(c_1-c_2)
            &\text{ otherwise}
        \end{cases}.
\]
Noting that $\sgn(c_1+c_2)=\sgn(c_1-c_2)$ whenever $|c_1/c_2|\geqslant1$,
the maximizer $y_\tau$ for $\partial\Reach(A,B)$ is
\begin{align*}
    y_\tau=x_\tau+x_\tau'
        &=\begin{cases}
            \begin{bmatrix}4+4(c_1/c_2)^{-3}\\-6(c_1/c_2)^{-2}\end{bmatrix}\sgn(c_1+c_2)
            &\text{if }c_1/c_2\leqslant -1\\
            \begin{bmatrix}4-4(c_1/c_2)^{-3}\\6(c_1/c_2)^{-2}\end{bmatrix}\sgn(c_1+c_2)
            &\text{otherwise}
        \end{cases}\\
        &=\begin{bmatrix}4-4(c_1/c_2)^{-3}\sgn(c_1/c_2)\\6(c_1/c_2)^{-2}\sgn(c_1/c_2)\end{bmatrix}\sgn(c_1+c_2)
\end{align*}
for $|c_1/c_2|\geqslant1$.

\section{Details on the second example}\label{sec:details_ex2_reach}

We consider the case where
\[
    A=\begin{bmatrix}-1&0\\0&-\sqrt{2}\end{bmatrix},
    \quad
    b_1=\begin{bmatrix}1\\-1\end{bmatrix},
    \quad
    b_2=\begin{bmatrix}1\\1\end{bmatrix},
    \quad
    B=\begin{bmatrix}1&1\\-1&1\end{bmatrix}.
\]
Note that $b_1$ and $b_2$ are the columns of $B$. Since all eigenvalues of $A$ are negative, it is stable.
Furthermore, one checks that $b_1$ and $Ab_1$
are linearly independent, hence $(A,b_1)$ is controllable, and similarly for $(A,b_2)$.
We can apply \Cref{thm:bdry_descrptn} to get the description of the boundary:
\begin{align*}
    \partial\Reach(A,b_1)
        &=\set*{\int_0^{\infty} e^{A t}b\sgn(c^Te^{A t}b)\dd t: c \in \RR^2\setminus \{\mathbf{0}\}}\\
        &=\Bigg\{\int_0^{\infty} \begin{bmatrix}e^{-t}&0\\0&e^{-\sqrt{2}t}\end{bmatrix}
            \begin{bmatrix}1\\1\end{bmatrix}\times\\
        &\hspace{0.5cm}\sgn\left(\begin{bmatrix}c_1&c_2\end{bmatrix}\begin{bmatrix}e^{-t}&0\\0&e^{-\sqrt{2}t}\end{bmatrix}
            \begin{bmatrix}1\\1\end{bmatrix}\right)\dd t: c \in \RR^2\setminus \{\mathbf{0}\}\Bigg\}\\
        &=\set*{\int_0^{\infty}\begin{bmatrix}e^{-t}\\e^{-\sqrt{2}t}\end{bmatrix}
            \sgn\left(c_1e^{-t}+c_2e^{-\sqrt{2}t}\right)\dd t: c \in \RR^2\setminus \{\mathbf{0}\}}.
\end{align*}
Given $c_1,c_2$ nonzero, observe that
\[
    c_1e^{-t}+c_2e^{-\sqrt{2}t}=0
    \;\Leftrightarrow\;
    1+\tfrac{c_2}{c_1}e^{(1-\sqrt{2})t}=0
    \;\Leftrightarrow\;
    t=\tfrac{1}{\sqrt{2}-1}\ln\tfrac{-c_2}{c_1}.
\]
Since only the ratio $c_2/c_1$ is important and $c_1$ must be nonzero, we can parametrize it as
$c_1=1$ and $c_2=-\alpha$, where $\alpha\in(1,+\infty)$, so that the only possible solution becomes
$t=t_1:=\tfrac{1}{\sqrt{2}-1}\ln \alpha\geqslant0$.
Now there are two cases:
\begin{itemize}
    \item if $c_2/c_1\geqslant -1$, then there is no solution and the integral becomes
        \[
            \int_0^{\infty}\begin{bmatrix}e^{-t}\\e^{-\sqrt{2}}\end{bmatrix}\sgn(c_1+c_2)\dd t
                =\begin{bmatrix}1\\\tfrac{1}{\sqrt{2}}\end{bmatrix}\sgn(c_1+c_2);
        \]
    \item  if $c_2/c_1<-1$, then we can split the integral into two parts (the sign must change):
        \begin{align*}
            \int_0^{t_1}&\begin{bmatrix}e^{-t}\\e^{-\sqrt{2}t}\end{bmatrix}\sgn(c_1+c_2)\dd t
                -\int_{t_1}^{\infty}\begin{bmatrix}e^{-t}\\e^{-\sqrt{2}t}\end{bmatrix}\sgn(c_1+c_2)\dd t\\
                &=\begin{bmatrix}1-e^{-t_1}\\\tfrac{1}{\sqrt{2}}-\sqrt{2}e^{-\sqrt{2}t_1}\end{bmatrix}\sgn(c_1+c_2)\\
                &=\begin{bmatrix}1-e^{-\tfrac{1}{\sqrt{2}-1}\ln\alpha}\\
                    \tfrac{1}{\sqrt{2}}-\sqrt{2}e^{-\tfrac{\sqrt{2}}{\sqrt{2}-1}\ln\alpha}\end{bmatrix}\sgn(c_1+c_2)\\
                &=\begin{bmatrix}1-2\alpha^{\tfrac{1}{1-\sqrt{2}}}\\
                    \tfrac{1}{\sqrt{2}}-\sqrt{2}\alpha^{\frac{\sqrt{2}}{1-\sqrt{2}}}\end{bmatrix}\sgn(c_1+c_2).
        \end{align*}
\end{itemize}
Hence the boundary of the reachable set is
\[
    \partial\Reach(A,b_1)=\set*{\pm\begin{bmatrix}1-2\alpha^{\tfrac{1}{1-\sqrt{2}}}\\
                    \tfrac{1}{\sqrt{2}}-\sqrt{2}\alpha^{\frac{\sqrt{2}}{1-\sqrt{2}}}\end{bmatrix}:\alpha\in[1,\infty)}
        \cup\set*{\pm\begin{bmatrix}1\\\tfrac{1}{\sqrt{2}}\end{bmatrix}}.
\]
The second reachable set is symmetric with respect to the vertical axis, hence we obtain
\[
    \partial\Reach(A,b_2)=\set*{\pm\begin{bmatrix}1-2\alpha^{\tfrac{1}{1-\sqrt{2}}}\\
                    \sqrt{2}\alpha^{\frac{\sqrt{2}}{1-\sqrt{2}}}-\tfrac{1}{\sqrt{2}}\end{bmatrix}:\alpha\in[1,\infty)}
        \cup\set*{\pm\begin{bmatrix}1\\-\tfrac{1}{\sqrt{2}}\end{bmatrix}}.
\]
In order to describe the border of $\partial\Reach(A,B)$, we consider the following
question: given a nonzero vector $\tau$, find the (unique by strict convexity) maximizer
in $\partial\Reach(A,b_1)$ in direction $\tau$:
\[
    x_\tau:=\argmax_{x\in \partial\Reach(A,b_1)}\Angle{x,\tau}.
\]
Observe that we have in fact already computed this point because the description of the border by
\Cref{thm:bdry_descrptn} is in the form of maximizers. If we write $\tau=(c_1,c_2)$
as above, then
\[
    x_\tau=\begin{cases}
        \begin{bmatrix}1-2(-c_2/c_1)^{\tfrac{1}{1-\sqrt{2}}}\\
            \tfrac{1}{\sqrt{2}}-\sqrt{2}(-c_2/c_1)^{\frac{\sqrt{2}}{1-\sqrt{2}}}\end{bmatrix}\sgn(c_1+c_2)
            &\text{ if }c_2/c_1\leqslant -1\\
        \begin{bmatrix}1\\\tfrac{1}{\sqrt{2}}\end{bmatrix}\sgn(c_1+c_2)&\text{ otherwise}.
        \end{cases}.
\]
A similar computation for $\partial\Reach(A,b_2)$ gives
\[
    x_\tau'=\begin{cases}
        \begin{bmatrix}1-2(c_2/c_1)^{\tfrac{1}{1-\sqrt{2}}}\\
            \sqrt{2}(c_2/c_1)^{\frac{\sqrt{2}}{1-\sqrt{2}}}-\tfrac{1}{\sqrt{2}}\end{bmatrix}\sgn(c_1-c_2)
            &\text{ if }c_2/c_1\geqslant 1\\
        \begin{bmatrix}1\\-\tfrac{1}{\sqrt{2}}\end{bmatrix}\sgn(c_1-c_2)
            &\text{ otherwise}
        \end{cases}.
\]
Noting that $\sgn(c_1+c_2)=-\sgn(c_1-c_2)$ whenever $|c_2/c_1|\geqslant1$,
the maximizer $y_\tau$ for $\partial\Reach(A,B)$ is
\begin{align*}
    y_\tau=x_\tau+x_\tau'
        &=\begin{cases}
            \begin{bmatrix}2-2(-c_2/c_1)^{\tfrac{1}{1-\sqrt{2}}}\\
                -\sqrt{2}(-c_2/c_1)^{\frac{\sqrt{2}}{1-\sqrt{2}}}\end{bmatrix}\sgn(c_1+c_2)
            &\text{if }c_2/c_1\leqslant-1\\
            \begin{bmatrix}2-2(c_2/c_1)^{\tfrac{1}{1-\sqrt{2}}}\\
                \sqrt{2}(c_2/c_1)^{\frac{\sqrt{2}}{1-\sqrt{2}}}\end{bmatrix}\sgn(c_1+c_2)
            &\text{otherwise}
        \end{cases}\\
        &=\begin{bmatrix}-2|c_2/c_1|^{\tfrac{1}{1-\sqrt{2}}}\\
            \sqrt{2}\left(1-|c_2/c_1|^{\frac{\sqrt{2}}{1-\sqrt{2}}}\right)\sgn(c_1/c_2)\end{bmatrix}\sgn(c_1+c_2)
\end{align*}
for $|c_2/c_1|\geqslant1$.


TITLE: Discrete Math Textbook Request
QUESTION [1 upvotes]: I am teaching a one-semester discrete math course this coming semester and I am having trouble finding a textbook appropriate for the structure of the course I plan to teach. My school currently is using Mathematical Structures for Computers Science by Judith Gersting, but this book is too long for a one-semester course.
Most textbooks that I've seen begin with a section on formal logic then the rest of the textbook consists of applications of this formal logic to sequences, series, graphs, matrices, etc. I have some reservations about this approach; the biggest being that for me personally, I learn best by building intuition through examples then learning the (more dry) theory afterwards.
I am currently looking at Fundamentals of Discrete Math for Computer Science by Jenkyns and Stephenson. I really like their approach to the subject, but I also have some concerns about their exposition. Many of the motivating examples have bawdy humor and mildly inappropriate remarks that remind the reader that computer science, historically, is a 'Boys Club.' I am worried about these remarks putting off students who are underrepresented in the subject. One particular example is:
"Throughout this text, we have written about algorithms - methods for doing computations or processing data.
\\not algorithms to tie your shores or find the G-spot" (page 405).
Similar examples are scattered throughout the book.
I have two questions:

Does anybody have any suggestions for books that are similar in organization to Jenkyns and Stephenson, but are more sensitive to issues of representation in STEM fields?
If not, what strategies could I use to teach around these problematic aspects of the book?

REPLY [0 votes]: Look at lecture notes by Edward A. Bender and S. Gill Williamson. This material is available in several forms (web, free pdf downloads, Dover) at cseweb.ucsd.edu/~gill/BWLectSite.
I don't know whether this material is organized as you wish or whether it teaches around the problematic aspects you note, but you might find it useful.