% jsr_decidability_frontier.tex

\subsection{Decidable island for robust switching stability}\label{sec:decidable-island-jsr}

In the general theory of switching systems and joint spectral radius (JSR), many natural decision problems are not decidable in full generality.
For instance, even boundedness questions for products of a fixed finite matrix set can be undecidable in broad rational classes \cite{blondel_tsitsiklis_2000}.
Accordingly, progress on ``where stability is decidable'' typically takes the form of identifying structurally constrained subclasses in which stability reduces to finite witnesses.

The certificate program developed here provides such a subclass.
Rather than attempting to decide \emph{JSR} in complete generality, we decide a stronger, certificate-based property: whether the instance admits a \emph{robust uniform contraction mechanism} that is both checkable and stable under perturbation.

\begin{definition}[Robust contraction certificate property]\label{def:ru-stable}
Fix a perturbation model and norm as in Section~\ref{sec:robust-certificate-ru-a}.
An instance satisfies \emph{\textup{RU-Stable}} if the pipeline returns a contraction certificate whose fields include:
\begin{itemize}
\item a tight aperiodic SCC $H$ on which the tight-core data are valid,
\item a Doeblin word witness $w$ with margin $\delta>0$ on the SCC face support,
\item a recurrence modulus (RC1) for $(H,w)$, yielding bounded-gap recurrence of $w$ along every tight minimizer in $H$,
\item an explicit projective contraction-rate pack $(\tau, C, \kappa)$,
\item an explicit robustness radius $\varepsilon^*>0$ such that all of the above remain valid (with degraded constants) for perturbations of size at most $\varepsilon^*$.
\end{itemize}
\end{definition}

\begin{theorem}[Decidability frontier in the certified class]\label{thm:decidable-frontier}
For every instance in the certified finite positive-template class considered in this paper, the pipeline terminates and returns exactly one of the following finite, verifiable artifacts.
\begin{itemize}
\item A \emph{finite obstruction witness} (OG1--OG4), certifying that the data required by Definition~\ref{def:ru-stable} cannot be obtained from the instance by the certificate rules.
In particular, OG4 returns an explicit directed cycle in the avoidance automaton, producing a tight periodic trajectory that avoids the Doeblin word forever.
\item A \emph{robust contraction certificate} establishing \textup{RU-Stable} for the instance, including an explicit robustness radius $\varepsilon^*$ and explicit rate degradation formulas.
\end{itemize}
Consequently, membership in the property \textup{RU-Stable} is decidable on this class.
\end{theorem}

\begin{remark}[Relation to JSR and switching stability]\label{rem:relation-jsr}
Theorem~\ref{thm:decidable-frontier} does not claim a decision procedure for JSR in unrestricted classes.
Instead, it identifies a concrete \emph{decidable island}: within the present positive-template setting, one can decide whether a robust, quantitative uniform contraction mechanism exists, and one can locate precisely where this mechanism fails via explicit witnesses.
This is consistent with, and complementary to, general undecidability barriers \cite{blondel_tsitsiklis_2000}.
\end{remark}
