% open_problem_resolution_map.tex

\subsection{Resolution map for neighboring open-problem families}\label{sec:open-problem-resolutions}

Several neighboring research programs study joint spectral radius, extremal products, ergodic optimization, and synchronization phenomena in broad generality.
In full generality many decision questions are provably undecidable, and many structural questions are answered only at the level of existence or genericity.
The present work contributes a complementary kind of result: a \emph{certificate calculus} that turns a range of these themes into finite objects whose validity is decidable on the certified positive-template class.

The table below records, for each commonly cited open-problem family, the concrete statement resolved \emph{within the certified class} and the pipeline artifact that realizes the statement.


\begin{table}[t]
\centering
\small
\setlength{\tabcolsep}{4pt}
\renewcommand{\arraystretch}{1.15}
\begin{tabular}{p{0.30\linewidth} p{0.46\linewidth} p{0.20\linewidth}}
\toprule
\textbf{Open-problem family} & \textbf{Resolved statement in the certified class} & \textbf{Pipeline artifact} \\
\midrule
Decidability of robust switching stability / JSR-type questions \cite{blondel_tsitsiklis_2000,kozyakin_jsr_bib}
&
Membership in \textup{RU-Stable} is decidable:
the pipeline returns either a robust contraction certificate (with $\varepsilon^*$ and explicit rate degradation) or an explicit obstruction witness (OG1--OG4), including the avoidance-cycle witness for recurrence failure (OG4).
&
\texttt{robust\_certificate} \newline
or \texttt{obstruction\_witness}
\\ \addlinespace

Mather-set structure for matrix sequences (ergodic optimization for JSR) \cite{morris_mather_2013}
&
The extremal set is represented effectively by a finite symbolic system:
a tight-core subshift (Definition~\ref{def:boundary-subshift}) refined by the avoidance/recurrence automaton (Section~\ref{sec:syndetic-recurrence}), yielding an explicit sofic description of extremal itineraries in the certified regime.
&
Tight-core graph $H$ \newline
+ avoidance automaton
\\ \addlinespace

Generic finiteness behavior for JSR and chamber regularity \cite{devil_staircase_ems}
&
Away from certificate-failure surfaces (notably $\gamma \to 0$ and $\delta \to 0$) the tight core and obstruction regime are locally constant (RU-B/RU-C), so extremal combinatorics and rates are stable on chambers.
Within a chamber, periodicity and recurrence are decided by the obstruction dichotomy.
&
$\gamma,\delta,\varepsilon^*$ \newline
+ chamber report
\\ \addlinespace

Devil's-staircase boundary complexity vs.\ tame regions \cite{devil_staircase_ems}
&
Complex behavior is confined to explicit boundary loci where the certificate margins collapse.
The robustness layer identifies and localizes these loci, separating stable chambers from boundary pathology by explicit, checkable inequalities.
&
Exceptional-set report \newline
(region mode)
\\
\bottomrule
\end{tabular}
\caption{How the robust certificate program resolves several open-problem families within the certified positive-template class (part 1).}
\label{tab:open-problem-resolutions-a}
\end{table}


\begin{table}[t]
\centering
\small
\setlength{\tabcolsep}{4pt}
\renewcommand{\arraystretch}{1.15}
\begin{tabular}{p{0.30\linewidth} p{0.46\linewidth} p{0.20\linewidth}}
\toprule
\textbf{Open-problem family} & \textbf{Resolved statement in the certified class} & \textbf{Pipeline artifact} \\
\midrule
Černý-type synchronizing bounds for induced automata \cite{slowly_sync_automata,synchronization_dfa}
&
For the specific automata generated by the certificate program (Doeblin-word search and avoidance automata),
the pipeline provides explicit state counts and either a bounded-gap modulus $B$ (acyclic avoidance) or an explicit cycle witness.
When the induced automata satisfy aperiodicity conditions that are checkable from the transition monoid, known special-class synchronizing bounds apply, yielding a quantitative reset bound for this subclass.
&
Automaton model \newline
+ modulus $B$ \newline
(+ optional reset bound)
\\ \addlinespace

Quantitative primitivity / length of a positive (Doeblin) product \cite{primitive_digraph_exponent}
&
The Doeblin-word search is finite and yields either a positive product witness with margin $\delta$ or a certificate of failure within the searched regime.
In the certified setting, digraph exponent bounds and state-size bounds convert this into an explicit worst-case search radius for positivity on the core block.
&
Doeblin witness word \newline
(length $L$, margin $\delta$)
\\ \addlinespace

Barabanov/extremal norm geometry and constructive computation \cite{barabanov_generic_unique}
&
A calibrated projective section together with recurrence (RC1) yields an explicit constructive extremal geometry:
a computable contraction mechanism and robustness neighborhood for the extremal dynamics.
This provides a concrete, checkable analogue of an extremal-norm project on the certified class.
&
Rate pack \newline
+ calibrated section \newline
+ robustness radii
\\ \addlinespace

Matrix-semigroup decision problems under bounded-language restrictions \cite{freeness_bounded_language}
&
The certificate program restricts products to a constrained language (tight-core admissible words plus avoidance constraints).
Within that restricted language, the key decision questions needed for stability reduce to finite automata and finite witnesses, giving an explicit decidability template compatible with bounded-language decidability phenomena.
&
Language model \newline
(tight-core + constraints)
\\ \addlinespace

Mapping undecidable vs.\ decidable frontiers for matrix products \cite{blondel_tsitsiklis_2000,kozyakin_jsr_bib}
&
The robust certificate contract isolates a decidable island and produces explicit exceptional sets where margins vanish.
This provides an operational frontier map: the pipeline states exactly which failures prevent certification and returns corresponding finite witnesses.
&
Frontier report \newline
(OG / RU margins)
\\
\bottomrule
\end{tabular}
\caption{How the robust certificate program resolves several open-problem families within the certified positive-template class (part 2).}
\label{tab:open-problem-resolutions-b}
\end{table}



\paragraph{Interpretation.}
The point is not to decide joint spectral radius in unrestricted families.
Instead, the paper identifies a structurally defined subclass in which the relevant stability and extremal-structure conclusions reduce to finite, checkable certificates.
The certificate margins then make these conclusions robust and enable region certification.
\paragraph{Decidability frontier for robust switching stability.}
Theorem~\ref{thm:decidable-frontier} gives a dichotomy:
either a robust certificate exists, producing explicit contraction rates and a robustness radius $\varepsilon^*$ (Definition~\ref{def:robust-certificate-object}),
or an obstruction witness exists (OG1--OG4), and the witness is finite and verifiable.
This realizes a decidable island inside the broader JSR landscape where global decision problems are known to be hard and can be undecidable \cite{blondel_tsitsiklis_2000}.

\paragraph{Effective Mather-set and extremal-language description.}
Within the certified class, the tight-core subshift (Definition~\ref{def:boundary-subshift}) and the avoidance/recurrence automata (Section~\ref{sec:syndetic-recurrence}) produce an explicit sofic model for extremal itineraries.
This is the finite-state analogue of the qualitative Mather-set structure developed in the ergodic-optimization literature \cite{morris_mather_2013}.

\paragraph{Generic periodicity and chamber stability.}
The chamber machinery (Section~\ref{sec:param-chambers}) states that, away from explicit tie and margin-collapse loci, the tight combinatorics and the obstruction regime are locally constant.
In those chambers, the pipeline decides whether extremals are periodic (unique tight cycle) or genuinely aperiodic (tight aperiodic SCC with certified recurrence), and it produces the corresponding finite model.

\paragraph{Devil's-staircase boundaries as certificate-failure surfaces.}
The region certification layer (Section~\ref{sec:ru-e}) turns the informal slogan ``complexity lives on the boundary'' into a checkable statement:
nontrivial parameter dependence can only occur where the robustness margins $(\gamma,\delta,\varepsilon^*)$ collapse.
This separates stable chambers from boundary pathology in a way that complements known devil's-staircase phenomena in broader families \cite{devil_staircase_ems}.

\paragraph{Synchronizing bounds for induced automata.}
The Doeblin search automaton (OG3) and the avoidance/recurrence automaton (OG4) are built explicitly and come with finite state counts.
In the acyclic-avoidance regime, the return modulus $B$ is computed (Algorithm~\ref{alg:syndetic}), which is already a quantitative recurrence statement.
When the induced machines fall into tractable synchronizing subclasses (aperiodic, trivial group in the transition monoid, or related checkable hypotheses), known Černý-type bounds become available for these induced automata \cite{slowly_sync_automata,synchronization_dfa}.

\paragraph{Quantitative bounds on Doeblin-word length.}
When a Doeblin block exists, the pipeline produces an explicit positive word and margin $\delta$ (OG3), and the robustness layer converts $\delta$ into contraction data.
In the certified setting, standard exponent bounds for primitive directed graphs can be used as plug-in upper bounds for the worst-case search radius on the core support \cite{primitive_digraph_exponent}.

\paragraph{Constructive extremal geometry and extremal-norm analogues.}
The calibrated section and rate pack (Section~\ref{sec:rate-pack-l}) provide a concrete geometric object that governs the extremal dynamics together with quantitative contraction and robustness radii.
This aligns with the extremal-norm narrative around Barabanov norms, but in the certified class the object is produced and verified by finite witnesses \cite{barabanov_generic_unique}.

\paragraph{Bounded-language semigroup decidability template.}
The certified language of admissible products is not arbitrary: it is the tight-core language refined by explicit avoidance constraints.
This is precisely the kind of language restriction under which semigroup problems can become decidable in settings where the unrestricted problems are intractable \cite{freeness_bounded_language}.

\paragraph{Frontier mapping and explicit witnesses.}
Finally, the obstruction taxonomy (OG1--OG4) and the robustness margins provide an operational map of why certification fails, returning concrete finite witnesses rather than leaving failure as an opaque non-result.
This is the main deliverable that makes the subclass practically usable: it either certifies stability with quantitative control or explains non-certifiability with an explicit obstruction.

\paragraph{Toward cover/atlas universality on compact normalized families within the certified class.}
Theorem~\ref{thm:global_universality_uniform} isolates the remaining step needed to upgrade from local robustness to a global statement on a compact region $\Theta$:
prove that the named margin-collapse loci are absent on $\Theta$ (equivalently: obtain uniform positive lower bounds for the certificate margins).
This can be achieved either by structural hypotheses that enforce uniform gaps, or by region mode plus a finite covering argument that certifies $\Theta$ and produces a global robustness radius.
If $\Theta$ intersects the named margin-collapse loci, the global procedure still terminates with a boundary-atlas report that localizes the degeneracy/obstruction region rather than asserting uniform contraction.
