Jsr Decidability Frontier

Decidable island for robust switching stability

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 [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 JSR in complete generality, we decide a stronger, certificate-based property: whether the instance admits a robust uniform contraction mechanism that is both checkable and stable under perturbation.

Definition — Robust contraction certificate property

Fix a perturbation model and norm as in Section .
An instance satisfies \emph{\textup{RU-Stable}} if the pipeline returns a contraction certificate whose fields include:

• a tight aperiodic SCC $H$ on which the tight-core data are valid,
• a Doeblin word witness $w$ with margin $\delta>0$ on the SCC face support,
• a recurrence modulus (RC1) for $(H,w)$, yielding bounded-gap recurrence of $w$ along every tight minimizer in $H$,
• an explicit projective contraction-rate pack $(\tau, C, \kappa)$,
• an explicit robustness radius $\varepsilon^*>0$ such that all of the above remain valid (with degraded constants) for perturbations of size at most $\varepsilon^*$.

Theorem — Decidability frontier in the certified class

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.

• A finite obstruction witness (OG1–OG4), certifying that the data required by Definition 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.
• A robust contraction certificate establishing \textup{RU-Stable} for the instance, including an explicit robustness radius $\varepsilon^*$ and explicit rate degradation formulas.

Consequently, membership in the property \textup{RU-Stable} is decidable on this class.

Remark — Relation to JSR and switching stability

Theorem does not claim a decision procedure for JSR in unrestricted classes.
Instead, it identifies a concrete 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 [blondel_tsitsiklis_2000].