Theorems

If $m\ne n$ , then $K_m$ and $K_n$ have different complete-match behavior.

State equality preserves every future

If $\delta^*(s_0,u)=\delta^*(s_0,u')$ , then for all $v\in\Sigma^*$ , $$uv\in L(\mathcal A)\quad\Longleftrightarrow\quad u'v\in L(\mathcal A).$$

Regular languages are closed under Boolean operations

If $L_1$ and $L_2$ are recognized by finite DFAs, then so are $L_1\cap L_2$ , $L_1\cup L_2$ , and $\Sigma^*\setminus L_1$ .

Residual recognition

The residual dynamic recognizes $L$ exactly.

Myhill–Nerode theorem, residual form

For a language $L\subseteq\Sigma^*$ , the following are equivalent: $L$ is recognized by a finite DFA; $L$ has finitely many left residuals; the relation $\equiv_L$ has finite index. When these conditions hold, the residual automaton is the unique minimal reachable DFA up to isomorphism.

The composition of continuous maps is continuous.

Finite intersection characterization

A space $X$ is compact if and only if every family of closed sets $\{C_i:i\in I\}$ with the finite intersection property has nonempty total intersection. The finite intersection property means $$C_{i_1}\cap\cdots\cap C_{i_k}\ne\varnothing$$ for every finite subfamily.

Let $X_n$ be a nonempty finite discrete space for every $n\in\N$ . Then $\prod_{n\in\N}X_n$ is compact.

Universal property of the inverse limit

Let $Y$ be a set and suppose maps $f_n:Y\to X_n$ form a compatible cone: $$\rho_{n+1,n}\circ f_{n+1}=f_n \qquad\text{for every }n.$$ There is a unique map $$f:Y\longrightarrow\varprojlim_nX_n$$ such that $\pi_n\circ f=f_n$ for every coordinate projection $\pi_n$ . If the spaces are topological and every $f_n$…

Closedness of compatibility

For continuous maps between Hausdorff spaces, the set of compatible threads is closed in $\prod_n X_n$ .

Finite discrete inverse-limit existence

Let every $X_n$ be a nonempty finite discrete space, with arbitrary bonding maps $\rho_{n+1,n}:X_{n+1}\to X_n$ . Then $\varprojlim_n X_n$ is nonempty.

Contraction fixed point

If $\mathcal B$ is complete and $F$ is a contraction, then $F$ has a unique fixed point. Starting from any $x_0$ , the iterates $x_{n+1}=F(x_n)$ converge to it.

If $F^r$ is a contraction on a complete metric space, then $F$ has a unique fixed point.

Dyck residual classification

The residuals of $D_k$ are precisely $$\{R_s:s\in\{1,\ldots,k\}^*\}\cup\{\varnothing\}.$$ Distinct stacks give distinct residuals.

Fixed-cut state minimum

The minimum number of reachable cut states in a deterministic strict layered recognizer is the number of distinct rows of $C_{m,n}$ .

Unique language from compatible cuts

Every compatible Boolean cut field determines a unique language $$L_C=\{w:C_{|w|,0}(w,\eps)=1\}$$ such that $$C_{m,n}(u,v)=\mathbf 1[uv\in L_C]$$ for every cut. Conversely, every language produces a compatible field.

Global adjacent plateau

If $q_L(N)=q_L(N+1)$ for some $N$ , then $L$ is regular and $Q_N(L)$ is the state set of its minimal residual DFA.

Basic access laws

For every language over a finite alphabet: $a_L(N)$ exists; $a_L(N)$ is nondecreasing in $N$ ; and if $L$ has a reachable $k$ -state DFA, then $a_L(N)\le k-1$ .

Observation-growth gap

If $L$ is nonregular, then $q_L(N)$ is strictly increasing and $$q_L(N)\ge N+2$$ for every $N\ge0$ . Equivalently, if $q_L$ ever fails to increase at an adjacent pair of horizons, then it remains bounded.

Bounded access characterizes regularity

For a language $L$ , the following are equivalent: $$L\text{ is regular} \quad\Longleftrightarrow\quad \sup_N a_L(N)<\infty \quad\Longleftrightarrow\quad a_L(N)\text{ is eventually constant}.$$

Exact access calculus for controlled Dyck presentations

For every finite controlled-Dyck presentation and every horizon $N$ , $$a_{L_M}(N)=\max_{K\in S_N}\alpha_{M,N}(K).$$ The quantity is effectively computable by finite balanced-distance relaxation, the stack recurrence above, and the finite controlled-Dyck shadow quotient. Moreover, $$\boxed{ a_{L_M}(N)\le\max\{1,(N+1)B_M+N\}. }$$…

The linear access certificate is pointwise sharp

For every horizon $N\ge0$ , some finite controlled-Dyck presentation attains the displayed upper bound. For every $N\ge1$ , one can arrange $B_M=2$ and $$a_{L_M}(N)=3N+2=(N+1)B_M+N.$$ The presentation is allowed to depend on $N$ .

Entry diameter is monotone under DFA quotient

For every such morphism, $$B_{M'}^{\mathrm{ent}}\le B_M^{\mathrm{ent}}.$$ Consequently the reachable minimal DFA of one fixed regular language has no larger entry diameter than any DFA recognizing that regular language.

Dyck-trace minimax certificate

For every controlled-Dyck language inside the fixed envelope $D$ , $$a_L(N)\le\max\{1,(N+1)\beta_D(L)+N\}.$$ The number $\beta_D(L)$ depends only on $L$ and the selected Dyck envelope, not on one chosen regular controller.

Balanced residual access lower bound

Every regular controller presenting $L$ satisfies $$B_M^{\mathrm{ent}}\ge\gamma_D(L),$$ and therefore $$\beta_D(L)\ge\gamma_D(L).$$

Entry-context residual lower bound

Every regular controller presenting $L$ satisfies $$B_M^{\mathrm{ent}}\ge\eta_D(L).$$ Consequently $$\boxed{ \beta_D(L)\ge\eta_D(L)\ge\gamma_D(L). }$$

Finite completion-summary saturation

For every controlled-Dyck language, $\eta_D(L)$ is exactly computable from any finite controller presentation by a terminating finite saturation.

Minimax sandwich stopping rule

If $b_M=\eta_D(L)$ , then the supplied presentation attains the global Dyck-trace minimum and $$\beta_D(L)=\eta_D(L)=b_M.$$ Both endpoints are computed by terminating finite procedures.

First-flip lower bound

Every regular controller presenting $L$ satisfies $$B_M^{\mathrm{ent}}\ge\tau_D(L),$$ and therefore $$\beta_D(L)\ge\tau_D(L).$$ Moreover, $\beta_D(L)=0$ exactly for $L=\varnothing$ and $L=D$ .

Punctured-threshold separation

For every $r\ge2$ , $$\boxed{ \tau_D(L_r^\circ)=2 <\gamma_D(L_r^\circ) =\beta_D(L_r^\circ)=2r. }$$

First-component contextual separation

For every $r\ge3$ , $$\boxed{ \tau_D(H_r)=2, \qquad \gamma_D(H_r)=4, \qquad \eta_D(H_r)=\beta_D(H_r)=2(r-1). }$$ In particular, $\beta_D(H_r)>\gamma_D(H_r)$ for $r\ge4$ .

Terminal-descent sewing collapse

For the trace $K_3$ , $$\boxed{\eta_D(K_3)=\beta_D(K_3)=4.}$$ The three-state presentation is state-minimal but not access-optimal.

Exact state/access frontier of $K_3$

(Exact state/access frontier of $K_3$ ). The minimum size of a controller presenting $K_3$ is three, and $$\nu_D(K_3;4)=6.$$ The nondominated state/access pairs are exactly $$\boxed{(3,6)\quad\text{and}\quad(6,4)}.$$

Terminal-descent family law

For every $m\ge2$ , $$\eta_D(K_2)=\beta_D(K_2)=4, \qquad \eta_D(K_m)=\beta_D(K_m)=2(m-1)\quad(m\ge3).$$

Even positional construction

For every even $m$ , an $(m+2)$ -state controller presents $K_m$ at the optimal entry cost $\beta_D(K_m)$ . At $m=4$ it is isomorphic to the six-state controller displayed above.

Exact access radius for square lengths

For every $m\ge0$ , $$a_{L_{\square}}(2m)=(m+1)^2+1, \qquad a_{L_{\square}}(2m+1)=(m+1)^2+2.$$

Exact depth-threshold profiles

Let $D_{k}^{\ge r}$ be the balanced words over $k$ bracket types whose stack height reaches at least $r\ge1$ . Then $$q_{k,r}^{\ge}(N) =1+\sum_{h=0}^{N}k^h +\sum_{h=\max(0,2r-N)}^{r-1}k^h,$$ $$a_{k,r}^{\ge}(N)=\max(2r,N).$$ For the complementary balanced language $D_k^{<r}$ that stays below $r$ ,…