Period convention

A positive integer $p$ is a period of $w=w_0\cdots w_{n-1}$ when

w_i=w_{i+p}\qquad(0\le i<n-p).

Periods longer than the word are therefore vacuous. For a fixed cap $B$ , write $P_B(w)=\{p\le B:p\text{ is a period of }w\}$ and $\operatorname{SmallPer}_B=\{w:P_B(w)\ne\varnothing\}$ .

FPRD-T82 · canonical quotient

The weakest monoid quotient for every bounded period

For words $u,v\in\Gamma^*$ , define

u\equiv_Bv \iff \forall x,y\in\Gamma^*\ \forall p\le B:\ xuy\in\operatorname{Per}_p \iff xvy\in\operatorname{Per}_p.

Each fixed-period language is regular, so this joint syntactic congruence has finite index. The quotient $M_B=\Gamma^*/{\equiv_B}$ recognizes every period predicate through $B$ . It is weakest in the exact algebraic sense: every monoid morphism recognizing all those languages factors onto $M_B$ .

A direct compositional cover stores

\sigma_B(w)= \bigl(\min(|w|,B),\operatorname{pre}_B(w), \operatorname{suf}_B(w),P_B(w)\bigr).

The prefix and suffix resolve every distance- $p$ comparison crossing a concatenation boundary. The period vector alone is not compositional: at $B=2$ , the words 01 and 10 have the same vector, but appending 0 separates them.

If $g=|\Gamma|\ge2$ , then

g^B\le |M_B| \le (B+1)\left(\sum_{i=0}^B g^i\right)^2 2^B.

Distinct length-B words are separated by a length-B right context, so exact generic storage requires $\Theta(B)$ bits for every fixed non-unary alphabet. On a unary alphabet, every word has every positive period and the quotient is trivial.

FPRD-T83 · rooted-type saturation

One rooted crossing type realizes every generic context

Consider a deterministic three-sweep transducer: the first and third sweeps are silent, while the middle right-to-left sweep copies the input. Every nonempty internal interval has the same idempotent three-loop effect and the same rooted reverse component.

An interval with spatial block $z$ has trace output $\operatorname{erase}_{\square}(z^{\rm rev})$ , so every output word occurs in this one type. Three adjacent spatial blocks

y^{\rm rev},\quad u^{\rm rev},\quad x^{\rm rev}

produce the trace $xuy$ . Therefore legal same-type equivalence coincides with the generic two-sided congruence:

u\equiv_B^{E,C}v\iff u\equiv_Bv.

Fixing the crossing sequences, flow, direction, component, and rooted side need not remove a single class of $M_B$ .

The long productive intervals in this witness are not output-minimal anchors. The theorem concerns bare rooted typing.

FPRD-T84 · marked-anchor lower bound

Two fixed output-minimal anchors still leave a linear-bit archive

In the same reverse-copy machine over $\Delta=\{0,1,\#\}$ , choose two named one-cell marker loops. They have the same rooted type, each emits $\#$ , and each is genuinely output-minimal. If the middle spatial word is $m^{\rm rev}$ , the complete output amid the anchors is

W(m)=\#\#m\#.

Right insertion acts by $R_m\cdot k=R_{mk}$ . For $K\ge4$ and $z\in\{0,1\}^{K-3}$ , let $W_z=\#\#z\#$ . The marker skeleton of $W_zW_z$ has period K and, by Fine–Wilf, no smaller period. Consequently

\operatorname{SmallPer}_K(W_{z'}W_z) \iff z'=z.

A legal insertion derived from z therefore distinguishes $R_z$ from all other payloads. The marked quotient has at least $2^{K-3}$ classes and at most $|M_K|$ , hence exactly $\Theta(K)$ bits of information.

FPRD-T85 · promise state complexity

Deterministic storage and existential mismatch certificates separate

Let $K=n+3$ , $W_x=\#\#x\#$ , and promise that the input lies in

D_n=\{W_xW_y:x,y\in\{0,1\}^n\}.

On this promise, having a period through K is exactly payload equality. Equality has a $2^n$ -element NFA fooling set, and either deterministic polarity must distinguish all first payloads. Thus equality is exponentially nondeterministic and both equality and inequality are exponentially deterministic.

Inequality is different: an NFA guesses a bit of the first payload, counts the next $n-1$ data symbols, and accepts when the corresponding bit of the second payload differs. This uses $2n+2$ states. Conversely, the reachable state sets after the prefixes $W_x$ form an antichain, so

2^n\le\binom{|Q|}{\lfloor|Q|/2\rfloor}.

Hence promise-NFA complexity for inequality is $\Theta(n)$ . The same comparison matrix supports an exponential deterministic archive but only a linear existential mismatch certificate.

The NFA is promise-relative and may accept malformed inputs. This is not a linear-state exact recognizer for the standalone framed language.

FPRD-T86 · exact finite-delay normal form

After (2B-2) letters, all surviving periods move together

Suppose $B\ge2$ , $|w|\ge2B-2$ , and $P_B(w)\ne\varnothing$ . If $d=\min P_B(w)$ , Fine–Wilf gives

P_B(w)=\{d,2d,\ldots,\lfloor B/d\rfloor d\}.

Every surviving period asks for the same next letter, $a_*(w)=w_{|w|-d}$ . Appending that letter preserves the entire profile; any other letter destroys it, and an absent period never returns under further extension.

A complete DFA therefore stores a short word verbatim until the horizon, then either enters a sink or retains the least period d and a rotating length-d delay window. The same transition graph recognizes $\operatorname{SmallPer}_B$ and its complement by swapping final states, with at most

1+\sum_{i=0}^{2B-3}|\Gamma|^i +\sum_{d=1}^{B}|\Gamma|^d

states. Over a non-unary alphabet the delay is exact. For $B\ge3$ , the word $0^{B-2}1\,0^{B-2}$ one step before the horizon has the nonprincipal profile $\{B-1,B\}$ , and its two next letters select different surviving branches. The case $B=2$ has a separate one-step transition witness; $B=1$ is the ordinary constant-word language and is not covered by the theorem.

FPRD-T87 · exact-language state complexity

A fixed ternary alphabet gives a linear NFA lower bound for the complement

Let $B\ge2$ and set

n=\left\lfloor\log_2\frac{B+2}{2}\right\rfloor, \qquad m=2^n, \qquad L=m-1, \qquad t=B-2m+3.

Over the single fixed alphabet $\Sigma_3=\{0,1,2\}$ , a recursive code $C_n:\{0,1\}^n\to\Sigma_3^L$ produces

U_x=C_n(x)2^t, \qquad V_y=C_n(\tau_ny), \qquad |U_xV_y|=B+1,

where $\tau_n$ flips the last bit. The construction realizes the comparison matrix

U_xV_y\in\operatorname{SmallPer}_B \iff x\ne y.

Why the selector works

If x and y first differ at coordinate i, the recursive prefix and twisted-suffix towers agree for $2^i-1$ symbols. This gives an off-diagonal border and therefore a period through B. On the diagonal, sibling codewords are mutually cross-bifix-free and have disjoint proper-period sets. Splitting possible borders into those contained in a codeword, those entering the separator, and those crossing the full separator excludes every nonempty proper border.

The length $B+1$ is important: every candidate period $p\le B$ is nonvacuous, so the argument uses the ordinary period convention without changing the language.

The polarity determines the NFA conclusion

For $\operatorname{Bad}_B=\Sigma_3^*\setminus \operatorname{SmallPer}_B$ , the matrix has identity polarity. Its m diagonal pairs form a standard NFA fooling set, so

\operatorname{nsc}(\operatorname{Bad}_B) \ge m =2^{\lfloor\log_2((B+2)/2)\rfloor} >\frac{B+2}{4}.

Every DFA for either polarity also needs at least m states. But the matrix for $\operatorname{SmallPer}_B$ has the complementary $J-I$ polarity. If an NFA with state set Q recognizes that language, the reachable sets at this cut form an antichain, yielding only

m\le\binom{|Q|}{\lfloor |Q|/2\rfloor}.

Thus the same selector gives a linear-in-B NFA lower bound for the complement, deterministic lower bounds for both languages, and a weaker Sperner bound for the original language. It does not give an m-state NFA lower bound for $\operatorname{SmallPer}_B$ .

This is an exact theorem about already exposed ternary words. It neither constructs legal transducer runs or inversions nor transfers the lower bound to the originating input language or device-size problem.

What the results do not imply

These results distinguish three tasks. The monoid $M_B$ supports arbitrary two-sided composition and preserves every individual bounded-period predicate. The finite-delay DFA recognizes only Boolean period existence under one-sided input. The transducer constructions show how much information remains after a particular output word or marked record has already been exposed.

None of them locates a successful run, chooses legal anchors, removes the run/inversion quantifiers, or constructs an equivalent one-way transducer. The remaining problem is the projection from input and run structure to the exposed record, not further compression of that record in isolation.

Bounded-period archives and recognition