2019–2023 structural background

Where the quotient relation holds—and where it breaks

We write $\amalg$ for the shuffle product throughout.

For ordinary regular expressions, Broda, Holzer, Maia, Moreira, and Reis's 2019 paper A Mesh of Automata maps each marked position to its prefix expression. Equality after unmarking gives a left-invariant equivalence, and the prefix automaton is the resulting quotient of the position automaton. Broda, Maia, Moreira, and Reis's 2021 paper The Prefix Automatongives the full correspondence and extends it to intersection.

Intersection is synchronized: both components move on the same letter. Its paired locations and paired prefix expressions retain that common label. Shuffle is asynchronous: either component may move while the other stays fixed. A shuffle location can therefore accumulate labelled recurrence from both components, even though every prefix state still ends in one letter.

Broda, Machiavelo, Moreira, and Reis's 2023 paper Location based automata for expressions with shuffle and intersection proves that the quotient relation can fail for shuffle; its Example 13 uses$((ab)^*)\amalg((bc)^*)$. The results below isolate a local obstruction, turn it into an exact classification for all starred-word shuffles, and reduce the smallest negative witness to two letter occurrences.

Broda, Machiavelo, Moreira, and Reis's other 2023 paper, Location automata for synchronised shuffle expressions, treats strong, arbitrary, and weak synchronized shuffle at the word level, constructs location and partial-derivative automata, and proves the latter is a quotient of the former. It does not define a prefix automaton for these operators. FPRD-SH-D02 below supplies the prefix convention needed to ask the corresponding quotient question for the strong and arbitrary operators. FPRD-SH-D03 gives the separate reversal-dual receipt needed by the weak operator. Both are FPRD extensions of that framework, not constructions attributed to the paper.

FPRD-SH-D01 · definition

The loop spectrum

For a letter-labelled NFA $A$and state $q$, define

$$\Lambda_A(q)=\{\sigma:q\xrightarrow{\sigma}q\}.$$

We use the broad existential state quotient: a block$C$ has a$\sigma$-transition to a block$D$ whenever some member of$C$ has such a transition to some member of $D$.

FPRD-SH-T01 · theorem

A quotient cannot delete loop labels

Loop preservation is elementary. Its use here is to expose a specific incompatibility between asynchronous locations and single-letter prefix states.

FPRD-SH-L01 · lemma

Prefix states are homogeneous

FPRD-SH-T04 · theorem

Incoming labels cannot disappear in a quotient

For a state $q$, define its incoming spectrum by

$$I_A(q)=\{\sigma:\exists p\;(p\xrightarrow{\sigma}q)\}.$$

This is stronger than the loop-spectrum test: the differently labelled predecessors need not be the target state, recurrent, or equal. Since prefix states are homogeneous, one APOS state with two incoming labels rules out every quotient immediately.

FPRD-SH-T05 · exact classification

The starred-word dichotomy

Here a starred-word shuffle means that each operand repeats one fixed nonempty word any number of times, while the shuffle may advance either operand at each step. The location and prefix automata are the constructions of Broda, Machiavelo, Moreira, and Reis.

The positive quotient is constructive but generally not left-invariant by this map. FPRD-SH-T06 below excludes every alternative left-invariant partition.

FPRD-SH-C03 · executable audit

The formulas survive exact structural checks

The verifier compares the recursively constructed prefix automaton with the quotient induced by the displayed formula—states, transitions, initial state, and final set—not merely language equivalence. The finite audit checks the implementation; the proof above supplies the all-length result.

Independent review: checker · exact output · audit certificate

FPRD-SH-T02 · theorem

Independent recurrence is fatal

For a convention that trims unreachable locations, the paired location must be reachable. The same condition is required when applying the argument inside a nested shuffle.

FPRD-SH-X01 · counterexample

The smallest nondegenerate witness

Let $a\ne b$ and set$\alpha=a^*\amalg b^*$. Write the location states as$0,A=(1,0),B=(0,2),C=(1,2)$. Every state is final.

The prefix automaton has the three final states$\varepsilon,X,Y$, with every state sending $a$ to$X$ and$b$ to$Y$. The location state$C$ carries both loop labels, so no quotient exists.

A nondegenerate shuffle needs at least one letter occurrence in each operand. This expression has exactly two, so it is occurrence-minimal in that class. By comparison, Example 13 of Broda, Machiavelo, Moreira, and Reis's 2023 paper has four letter occurrences.

Independent review: checker · exact output · audit certificate

FPRD-SH-T03 · theorem

What the stronger left quotient requires

For a candidate projection$\pi:Q_A\twoheadrightarrow P$, define the predecessor-block profile

$$\operatorname{Pred}^{\pi}_{\sigma}(q) =\{\pi(r):r\xrightarrow{\sigma}q\}.$$

This is right invariance on the reversed automaton, written in predecessor form. It is a complete test for a fixed candidate partition.

FPRD-SH-T06 · exact classification

No starred-word shuffle has a left quotient

An ordinary quotient only asks whether each target edge is the image of some source edge. A left-invariant quotient is stricter: source states merged into one target state must also have the same incoming history after predecessors are replaced by their quotient blocks.

Together with FPRD-SH-T05, this closes the ordinary-versus-left quotient classification for the entire starred-word family.

Independent review: checker · exact output · audit certificate

FPRD-SH-X02 · sharp control

The smallest unary case exhibits the exceptional defect

For $a^*\amalg a^*$, merging the three noninitial locations gives the two-state prefix automaton. Thus an ordinary quotient exists.

It is not left-invariant. A one-coordinate location has the initial state as an $a$-predecessor, while the two-coordinate location does not. Those states must be merged to obtain the prefix automaton, but their predecessor-block profiles disagree.

Distinct loop labels are therefore sharp for ruling out every quotient. Their absence does not restore the left-invariant quotient architecture established in A Mesh of Automata and The Prefix Automaton. FPRD-SH-T06 shows that this is the first case of an all-length obstruction, not an isolated small example.

FPRD-SH-C01 · exact reproduction

The published example is recovered exactly

A structural checker implements Example 13 of Broda et al.'s location-automata paper, marked prefix recursion, unmarking, existential quotients, and predecessor-profile tests. For$((ab)^*)\amalg((bc)^*)$, it reconstructs the following counts and exhausts all compatible partitions.

No existential state quotient maps the location automaton onto the unmarked prefix automaton.

FPRD-SH-C02 · bounded census

Quotient failure is common in the tested family

The same checker exhausts every$x^*\amalg y^*$ over$\{a,b,c\}$ with nonempty words and total word length at most four.

All 18 ordinary-quotient cases are unary controls in which both operands repeat the same letter. This census was the discovery record for FPRD-SH-T05; the theorem above now proves its pattern at every length.

FPRD-SH-D02 · FPRD definition

A last-event prefix convention for synchronized shuffle

Broda, Machiavelo, Moreira, and Reis's synchronized-shuffle frameworkdistinguishes three word operations. Under strong synchronization on$\Gamma$, letters in$\Gamma$ must be read jointly. Under arbitrary synchronization, a matching synchronized letter may be read jointly or by either component alone. Theweak operator permits one component to consume a synchronized letter alone, but prevents the other component from doing so before the next joint event resets that memory.

To form the prefix target studied here, FPRD extends the usual backward last-event recursion. For strong synchronization, a solo terminal event is admitted only outside$\Gamma$, while a paired terminal event is admitted only when both components end in the same letter of $\Gamma$. For arbitrary synchronization, the solo clauses remain unrestricted and the paired clause is added. The ordinary$R_\varepsilon$ recursion is then applied to these terminal-event clauses.

This synchronized prefix convention is an FPRD definition. The Broda et al. supply the word operations and location automata; the quotient results below concern their pairing with this explicit last-event target.

FPRD-SH-T07 · exact classification

Strong unary synchronization restores the left quotient

“Accessible” is essential: the syntactic product universe also contains unreachable off-diagonal locations, and they are not silently deleted inside a quotient.

FPRD-SH-T08 · exact classification

Arbitrary unary synchronization has an atomic left boundary

Here arbitrary means that each occurrence of$a$ may be consumed by the left component, the right component, or both components jointly.

FPRD-SH-C04 · executable audit

The synchronization thresholds survive exact checks

These computations compare exact states, transitions, initial and final sets, quotient images, and predecessor profiles. They audit the formulas; the all-parameter conclusions come from the proofs.

A separate implementation reconstructs the automata from their event rules and compares both automata with an independent word-level oracle in 4,536 bounded cases. See the independent output, checker, and audit certificate.

FPRD-SH-B01 · resolved boundary

Weak synchronization needs a backward-memory receipt

Broda, Machiavelo, Moreira, and Reis's weak location construction carries forward memory sets $\Delta,\Lambda$: they record which synchronized letters have occurred solo since the previous joint event. A prefix construction runs the structural question in the opposite direction. It must certify which solo synchronized letters may occur before the next joint event.

Reusing the forward memory as though it were already this backward receipt leaves the prefix states and transitions under-specified. The next result discharges this requirement by defining the receipt through reversal, rather than identifying the two directions silently.

This boundary remains useful: the weak construction below depends on the reversal proof, not on treating forward history as backward prefix data.

FPRD-SH-D03 · FPRD definition theorem

The backward receipt is the reversal dual

Let $\bowtie_{\Gamma,D,E}$ be the auxiliary weak shuffle defined by Broda et al., where$D,E$ remember one-sided synchronized letters since the previous joint event. Define

$$u\overleftarrow{\bowtie}_{\Gamma,D,E}v =\{z^R:z\in u^R\bowtie_{\Gamma,D,E}v^R\}.$$

The same sets now describe one-sided letters before the next joint event. Peeling a joint terminal letter resets both sets; peeling a left-only terminal letter adds it to$D$ and is forbidden when it is already in $E$; the right-only rule is symmetric.

This defines an FPRD weak prefix extension. It is not attributed to the cited source paper.

FPRD-SH-T09 · exact classification

Weak unary synchronization always restores an ordinary quotient

Write prefix states as$P^b_{i,j}$, with receipt$b\in\{N,L,R\}$. Write location states as left and right boundary states$X_i,Y_j$ and paired states$Z^b_{i,j}$. The quotient is

The receipt letter records the permitted one-sided run before the next joint event: $N$is neutral, $L$ records a left-only run, and $R$records a right-only run.

$$X_i\mapsto P^L_{i,0},\quad Y_j\mapsto P^R_{0,j},\quad Z^N_{i,j}\mapsto P^N_{i,j},\quad Z^L_{i,j}\mapsto P^L_{i,j+1},\quad Z^R_{i,j}\mapsto P^R_{i+1,j}.$$

FPRD-SH-T10 · exact impossibility

Weak unary synchronization never restores a left quotient

FPRD-SH-C05 · executable audit

The weak classification survives exact checks

The finite checks audit the shifted seams and the exceptional case. The all-parameter conclusions come from the proofs.

The independent review also reconstructs all 1,024 quotient cases, all 256 subset orbits, and the exceptional$(1,1)$ transient. Its outputis accompanied by the checkerand certificate.

FPRD-SH-T11 · arbitrary-arity transfer theorem

Memoryless Boolean products preserve componentwise left quotients

In Broda, Machiavelo, Moreira, and Reis's 2026 Boolean-product construction, each letter has a family of allowed nonempty participant sets. A transition advances exactly the participating components and leaves the others fixed. The policy is memoryless when that family depends only on the letter, not on earlier events.

Following Broda, Holzer, Maia, Moreira, and Reis's definition, an equivalence is left-invariant when its initial set is a union of equivalence classes and equivalent target states have the same predecessor classes for every letter. The quotient automaton has those classes as its states.

The 2026 paper establishes the corresponding right-invariant product architecture. Reversal gives the theorem above as its left-handed dual: an event run keeps the same participant sets in reverse order, so no additional state is needed. This contrasts with weak synchronization, where event legality depends on earlier one-sided events.

The independent review checks every two-state unary transition structure and binary support policy in the stated finite domain, including all admissible initial and final boundary sets. The arbitrary- arity conclusion comes from the proof, not that enumeration.

FPRD-SH-B02 · exact construction boundary

There are two different prefix constructions

For ordinary component expressions, the classical position-to-prefix quotients and FPRD-SH-T11 give a canonical left quotient

$$\Vert_\psi(A_{\mathrm{POS}}(e_i)) \twoheadrightarrow \Vert_\psi(A_{\mathrm{Pre}}(e_i)).$$

That target need not be the natural prefix automaton obtained by applying the backward prefix recursion to the single combined Boolean-product expression. Pure shuffle$a^*\amalg b^*$ is already a counterexample: its natural prefix automaton is not any quotient of its location automaton, while the componentwise quotient above exists.

The next theorem resolves this comparison for flat memoryless Boolean-product expressions.

FPRD-SH-T12 · exact construction theorem

The natural prefix automaton is an event-signature expansion

An incoming event signature of a product state is a pair$(a,S)$: the last global event read $a$ and advanced exactly the components in the allowed support$S$. Write$\operatorname{Sig}(q)$ for the signatures of useful edges entering$q$.

The direction matters: before unmarking, the natural construction is generally a refinement of the component-prefix product, not a quotient of it.

FPRD-SH-T13 · expression-specific iff criterion

Agreement means one possible last event per product state

If one useful target has two signatures, the marked natural automaton has strictly more states and cannot be any quotient of the product. After erasing position marks, uniqueness remains a sufficient condition. The converse for one particular unmarked expression can fail because erasure may merge signature copies; the next theorem gives the exact policy-level statement that is uniform over all component expressions.

FPRD-SH-T14 · sharp universal classification

Pairwise-overlapping unique supports are necessary and sufficient

Combining the prefix construction with the Boolean-product support policy, call a memoryless policy signature-rigid when every active letter $a$ has exactly one support $S_a$, and$S_a\cap S_b\ne\varnothing$whenever $a\ne b$.

Full synchronization is one positive case, but not the whole class. At arity three, supports$\{1,2\},\{2,3\},\{1,3\}$are pairwise intersecting and therefore work even though no participant belongs to all three. Pure shuffle is the negative control: its singleton supports violate uniqueness or pairwise intersection.

An independent exhaustive review covers all 16,452 two-letter support policies at arities one through three, separates every one of the 16,382 non-rigid policies, and checks the same-letter unmarked boundary for 172,128 support-pair occurrences. The cited papers supply the component constructions; no literature-priority claim is made for this classification.

FPRD-SH-T15 · exact state-complexity theorem

A support graph gives the exact worst-case local split

Form a graph $C_\psi$ whose vertices are the allowed event signatures$(a,S)$. Two distinct signatures are adjacent when they have the same letter or their supports are disjoint.

The earlier signature-rigidity theorem is the endpoint$\omega(C_\psi)=1$. The full clique number measures how far a non-rigid policy can split one canonical state.

This is a worst-case statement over component expressions, not a claim that every expression realizes the clique number. The starred construction proves attainability by assigning one homogeneous letter to each participant used by a maximum clique.

FPRD-SH-T16 · complexity classification

Exact policy-only prediction is NP-complete

The hardness concerns prediction from a variable-arity policy. When one fixed useful product is already explicit, its incoming signatures can still be enumerated directly from its edges.

FPRD-SH-T17 · exact global state-count identity

Total overhead is target-set collision excess

For each event signature $\sigma$, let $T_\sigma$ be the useful product states entered by an edge with that signature.

The pairwise intersection sum is always an upper bound. It is exact precisely when no useful product state receives three or more signatures; triple collisions require the alternating inclusion–exclusion corrections.

For example, if three target sets contain the same single state, that state contributes $3-1=2$to the true overhead but $\binom32=3$to the pair sum. The triple intersection subtracts the excess one.

FPRD-SH-T18 · exact finite-size theorem

Independent support blocks have a closed total-overhead formula

Suppose each active letter has one support and the active supports are pairwise disjoint. Let $B_a$be the useful synchronous block advanced by letter$a$, with$N_a=|Q(B_a)|$ and$M=\prod_aN_a$. Write$r$ for the number of active letters, equivalently the number of independent blocks.

Ordinary $r$-ary pure shuffle is the singleton-support case, so$N_i=m_i$ for component state counts $m_i$. The earlier clique bound exceeds the exact answer by$\sum_a M/N_a-r$. The gap is positive when there are at least two active blocks and at least one block has more than one state. With one active block, both the exact overhead and clique bound are zero. For fixed$r\ge2$, the coefficient$r-1$ is asymptotically sharp as all block sizes grow.

Overlapping one-support policies do not factor into independent blocks. Their exact prescribed-size maximum remains open.

FPRD-SH-T19 · exact sparse compilation

Policy compatibility compiles exactly into colored exact cover

Give every policy signature $\sigma=(a,S)$one primary selector with an on and an off option. Its on option contains each participant in $S$as a nonprimary item colored by $a$.

Knuth's 2000 Dancing Linkspaper supplies the reversible sparse-update technique; his later DLX2 implementation supplies the color semantics used here. DLX2 can therefore enumerate the compatible signature families without constructing the canonical product. For a fixed expression, compatibility is only the policy layer: the corresponding target intersection can still be empty or contain no useful state.

FPRD-SH-T20 · exact automata-to-matching correspondence

A depth-one Boolean product exposes the complete matching core

For a graph $G=(V,E)$, give each edge $e$ its own letter$a_e$ and support, and give vertex $v$ the component expression$R_v=\varepsilon+\sum_{e\ni v}a_e$.

FPRD-SH-T21 · exact counting-complexity boundary

Product-free enumeration is exact—but counting remains hard

A size-$k$ matching has exactly$k-1$ overhead witnesses. Adding one isolated edge yields the displayed recovery identity. Membership in #P uses a matching of size at least two together with one distinguished edge other than its least edge; a size-$k$ matching has exactly$k-1$ such witnesses. Valiant's theorem that counting all graph matchings is #P-complete and the two-call identity then prove completeness under polynomial-time Turing reductions. Dancing Links remains a useful sparse reversible enumerator, but this theorem does not turn exact evaluation into a polynomial-time computation.

FPRD-SH-T22 · exact uniform-support stability transfer

Kneser independence gives two sharp zero-overhead ceilings

Give every letter one distinct support in$\mathcal F\subseteq\binom{[n]}r$. FPRD-SH-T14 says the policy has zero overhead for every compatible component tuple exactly when these supports intersect pairwise. Equivalently, $\mathcal F$ is an independent set of the Kneser graph$KG_{n,r}$.

In the Hilton–Milner range the largest empty-core zero-overhead policies are known exactly, including their equality shapes. For$r\geq4$, fix$x\notin A\in\binom{[n]}r$, include $A$, and include every$r$-set through$x$ that meets$A$. For$r=3$, the second equality type consists of all triples meeting a fixed triple in at least two points; for $r=2$, it is a triangle.

The boundary $n=2r$ is genuinely different. Each support is disjoint only from its complement, so choosing one member of every complementary pair gives a maximum zero-overhead family. Many such maximum families have no common participant when$r\ge2$; the star/non-star gap disappears. The case $n<2r$is simpler still: the Kneser graph has no edges, and the full support family is zero-overhead.

The extremal inequalities and equality cases are the classical Erdős–Ko–Rado and Hilton–Milner theorems. The FPRD result is their exact transfer to the universal natural-prefix overhead question.

FPRD-SH-T23 · quantitative collision receipt

Above the ceiling, the Kneser spectrum counts forced witnesses

Assume $1\le r\le n/2$. Write$N=\binom nr$,$d=\binom{n-r}r$,$\tau=\binom{n-r-1}{r-1}$, and $\alpha=\binom{n-1}{r-1}$. If $m=|\mathcal F|>\alpha$, then the number of unordered disjoint support pairs satisfies

$$\operatorname{dp}(\mathcal F) \geq \left\lceil \frac{d+\tau}{2N}\,m(m-\alpha) \right\rceil.$$

In the one-shot construction of FPRD-SH-T20, size-two support matchings are exactly these disjoint pairs, while every larger matching contributes additional nonnegative overhead. Therefore the same expression is a policy-size-only lower bound on one-shot natural-prefix overhead.

This general spectral receipt is not claimed sharp. The supersaturation literatureobtains stronger and sometimes exact disjoint-pair minima in restricted parameter ranges.

FPRD-SH-T24 · quantitative diversity receipt

A near-star hub forces a block of automata obstructions

Let $m$ be the number of supports,$d$ the largest number containing one participant, $\gamma=m-d$, and$q$ the number of disjoint support pairs.

Each counted pair is an executable two-letter prefix-splitting receipt. Unlike the global spectral bound, this certificate can activate already near the Hilton–Milner non-star threshold.

FPRD-SH-T31 · exact diversity-parameterized factorization

The closest star supplies an exceptional search kernel

Choose a maximum-degree participant $x$. Let $\mathcal A$ be the supports containing it—called the participant star—and let$\mathcal B$be the diversity$\gamma$ supports that avoid it. This uses Kupavskii's diversity parameter, but the factorization below is the FPRD automata deduction. Because every member of $\mathcal A$contains $x$, a compatible signature family—one whose supports are pairwise disjoint—contains at most one of them. Write$\mathcal M(\mathcal B)$ for the pairwise-disjoint subfamilies of$\mathcal B$.

Substituting these two forms into the exact target-set inclusion–exclusion formula computes global natural-prefix overhead with at most$O(|\mathcal F|2^\gamma)$calls to the target-intersection oracle. The canonical component product is not enumerated. This bound counts oracle calls; an implementation must separately account for the representation and intersection cost of its target sets.

This is a target-oracle theorem. Equal policy conflict patterns do not force equal expression-dependent target sets, so the reachability and usefulness oracle remains necessary. A closest star is convenient but need not minimize the exceptional side; the optimal intersecting-core decomposition appears below.

FPRD-SH-T32 · exact one-shot algorithm and quotient

Conflict masks and a zeta transform remove the oracle

In the depth-one, or one-shot, model, each component letter can occur at most once, so product states are pairwise-disjoint support families, equivalently support matchings. For an exceptional matching $N$, let $c(N)$ count hub supports disjoint from its union. The full matching polynomial splits as

$$Z_{\mathcal F}(z)=Z_{\mathcal B}(z) +z\sum_{N\in\mathcal M(\mathcal B)}c(N)z^{|N|}.$$

Index the exceptional supports by$[\gamma]$ and assign each hub support its conflict mask$\mu(A)=\{j:A\cap B_j\ne\varnothing\}$. If $w_M$ is the number of hub supports with mask $M$, then

$$c(N)=\sum_{M:M\cap N=\varnothing}w_M =W([\gamma]\setminus N),$$

where $W$ is the subset-zeta transform of$w$: it precomputes, for every set of exceptional indices, the total weight of all of its submasks. This gives exact one-shot overhead in$O(|\mathcal F|r\gamma+\gamma2^\gamma)$time and $O(2^\gamma)$auxiliary space.

FPRD-SH-T33 · optimal intersecting-core decomposition

Any intersecting core gives the same exact factorization

Let $\mathcal C\subseteq\mathcal F$be any pairwise-intersecting support family and put$\mathcal B=\mathcal F\setminus\mathcal C$,$k=|\mathcal B|$. A support matching contains at most one member of$\mathcal C$. Therefore the target factorization and the one-shot conflict-mask/zeta algorithm above hold verbatim with $k$in place of $\gamma$.

$$\kappa(\mathcal F)=\tau(D_{\mathcal F}) =|\mathcal F|-\max\{|\mathcal C|:\mathcal C\text{ is pairwise intersecting}\} \le \gamma(\mathcal F),$$

where $D_{\mathcal F}$ joins disjoint supports. Thus a minimum vertex cover gives the smallest exceptional side among decompositions obtained from one pairwise-intersecting core. A maximum participant star merely supplies one feasible cover.

The displayed running times assume that a cover is supplied. Computing a minimum cover has its own parameterized cost; for comparison, Harris and Narayanaswamy give a modern fixed-parameter vertex-cover algorithm. The theorem does not assert that this decomposition is optimal among all possible exact-overhead algorithms. It also does not solve expression reachability. In the long-standing binary shuffle state-complexity problem, the support kernel is already constant-size; the unresolved work lies in the target/reachability oracle.

A trace-counting test makes the sequential boundary exact. The published DFA problem is$\#\mathrm P$-complete with one commuting edge and hence $\kappa=1$, while the one-Foata-step fragment has a direct$O(|\Sigma|\kappa2^\kappa m)$algorithm. See thetrace-cover boundary.

FPRD-SH-B10 · corrected parameter boundary

Diversity can exceed the best intersecting-core kernel without bound

For a prime power $q$, take the lines of the finite projective plane$PG(2,q)$ as supports on its points. Every two lines meet, so the whole family is an intersecting core and $\kappa=0$. There are $q^2+q+1$ lines and each point lies on $q+1$ of them; these standard incidence facts are documented in Dembowski's Finite Geometries. Hence

$$\gamma=q^2,\qquad \kappa=0.$$

Diversity remains a meaningful extremal parameter and a correct supplied kernel. It is not the canonical exact-search parameter. The smallest control is the triangle$\{12,13,23\}$, where$(\gamma,\kappa)=(1,0)$.

FPRD-SH-C18 · exact corrected-kernel audit

Minimum-cover and direct collision calculations agree

All checks pass and a complete rerun is byte-identical. The arbitrary-parameter result is proved above; the finite audit validates the implementation and boundary examples.

A separate implementation exhaustively checks 16,384 support families of size at most seven on four participants, covering 181,196 matching states and 1,776 strict improvements over the closest-star diversity parameter. It also reconstructs the projective planes of orders 2, 3, and 5 directly over finite fields.

Independent review: checker · exact output · audit certificate

FPRD-SH-B09 · sharp scope boundary

Exponential search output is not an arithmetic lower bound

• Uniform families can realize all $2^\gamma$ conflict-mask classes, so the canonical quotient-size bound is exact.
• $\gamma+1$ pairwise-disjoint supports have diversity $\gamma$ and $2^{\gamma+1}$ XCC solutions. Any enumerator that emits them all has exponential output.
• The same disjoint family has the closed overhead $(\gamma-1)2^\gamma+1$. Therefore the output example does not prove that evaluating the final number requires exponential time.

FPRD-SH-C17 · exact diversity-kernel audit

Direct collision counts and both kernel algorithms agree

A second complete run is byte-identical. The finite audit supports the implementation; the arbitrary-parameter conclusions come from the proofs above.

The review certificate, independent verifier, and exact output provide a separate implementation over 1,088 complete families and 250 deterministic larger controls.

FPRD-SH-C11 · exact extremal and spectral audit

The phase boundary and equality families survive exact enumeration

Every check passes. The arbitrary-size statements come from the exact automata reduction, the cited classical theorems, and the spectral proof.

The independent review certificate, checker, and exact output add hostile tests below the EKR range, at$n=2r$, and at$r=1$. Those tests exposed the missing hypotheses now stated in FPRD-SH-T22 and FPRD-SH-T23.

FPRD-SH-T25 · exact graph-product correspondence

Cartesian support tensors produce strong graph powers

Let $J_\psi$ join distinct signatures whose nonempty supports overlap. Independent sets in this graph are pairwise-disjoint support families, so the maximum local signature split is$\Omega(\psi)=\alpha(J_\psi)$.

On participant universe $U^k$, define the tensor support

$$S_{(a_1,\ldots,a_k)}=S_{a_1}\times\cdots\times S_{a_k}.$$

FPRD-SH-T26 · exact asymptotic invariant

Support-packing capacity is Shannon capacity

Define the asymptotic packing rate of Cartesian support tensors by

$$\Omega_\infty(\psi)=\sup_{k\ge1}\Omega(\psi^{\otimes k})^{1/k}.$$

Every finite simple graph occurs as$J_\psi$ for a uniform policy: represent each graph edge by one token shared by its endpoints, then add private tokens until every support has the common positive size $\max(1,\Delta(G))$. The maximum with one is essential for edgeless graphs: it preserves the theorem's nonempty-support hypothesis. The unrestricted asymptotic policy problem therefore contains general Shannon capacity; useful leverage must come from structured policy families.

This is a policy/graph dictionary, not an expression compiler. A signature of $\psi^{\otimes k}$is already a vertex of the strong power. Whether a prefix automaton over the original signatures can realize a correlated code is a separate reachability question, answered for the pentagon only in FPRD-SH-X04 below.

FPRD-SH-B03 · published graph-capacity boundary

Nondivisible complements of Kneser graphs retain a capacity gap

For the complete $r$-uniform policy,$J_\psi=\overline{KG_{n,r}}$. Kneser graphs themselves have capacity equal to their EKR independence number, so no asymptotic gap remains there. When$r\mid n$, the complement also collapses at one use with capacity$n/r$. When$r\nmid n$, the one-shot packing$\lfloor n/r\rfloor$ and the fractional/Lovász ceiling $n/r$diverge.

The smallest complete two-support case is the triangular graph$T_5=\overline{KG_{5,2}}$. The published finite powers give

$$\alpha(T_5),\alpha(T_5^{\boxtimes2}), \alpha(T_5^{\boxtimes3}),\alpha(T_5^{\boxtimes4}) =2,5,12,27,$$

At the next layer, supermultiplicativity gives$12\cdot5=60$, while the recursive upper bound used by Kizhakkepallathu, Östergård, and Popa gives$\lfloor(5/2)\cdot27\rfloor=67$. Hence $60\le\alpha(T_5^{\boxtimes5})\le67$; no exact fifth-power value is claimed here.

The general finite-attainment question is already settled negatively; recent work gives infinitely many connected nonattaining graphs. It is not listed here as an open problem.

FPRD-SH-C12 · exact Shannon-bridge audit

The tensor and universality compilers survive complete small tests

Independent checker · verification output · audit certificate

FPRD-SH-T27 · policy-level no-amplification criterion

Perfect overlap policies finish support packing in one layer

By Lovász's perfect graph theorem, the complement of a perfect graph is perfect, so$\alpha(J)=\chi(\overline J)$. Combining this with the Lovász-theta sandwich$\alpha\le\Theta\le\vartheta\le\chi(\overline J)$collapses every inequality to equality. This gives a useful support-policy gate: perfect overlap graphs need no finite-power packing search. Pure shuffle has an empty overlap graph and full synchronization a complete one, so both have exactly multiplicative support-tensor behavior. The statement does not classify the languages or reachable states of arbitrary expressions using those policies.

FPRD-SH-X03 · strict support-tensor amplification

A five-cycle support tensor packs five where layers pack four

Put five participants on a cycle and let letter$a_i$ advance the adjacent pair$\{i,i+1\}$. Its support-overlap graph is $C_5$.

The five tensor signatures$\{(i,2i\bmod5):i\in\mathbb Z_5\}$are pairwise compatible. This is Lovász's classical pentagon codein support-policy notation. By itself it says nothing about reachability in a prefix automaton: each displayed pair is already a tensor letter. The expression-level construction is separate.

FPRD-SH-B04 · open cyclic-policy rate

The seven-cycle support rate remains a graph-capacity boundary

The same adjacent-pair policy on seven participants has$J_\psi=C_7$, hence$\Omega_\infty(\psi)=\Theta(C_7)$. Buys, Polak, and Zuiddam's Lean-verified recursive construction gives an explicit code in the two-hundredth strong power and therefore

$$3.258805369885\ldots \leq\Omega_\infty(\psi)<3.3177.$$

No improvement to those graph-capacity bounds is claimed, and the support-tensor identity does not make this an expression theorem. The five-dimensional base gadget is now compiled separately below: a table-free path generator reconstructs the published 367-code, and residual minimization gives a 128-state partial DFA. This is a succinctness result for a known slice. A new capacity result still requires an emitted finite slice that improves a published bound.

The complementing-permutation compiler is not the route to this result. $C_5\cong\overline{C_5}$, but $C_7\not\cong\overline{C_7}$: the two graphs have degrees two and four. Thus the square compiler calibrates self-complementary families such as Paley graphs, while the seven-cycle requires the five-coordinate path construction.

FPRD-SH-T28 · reachable expression compiler

A complementing relabelling compiles a twisted section

Let a one-support-per-letter policy have overlap graph$G=J_\psi$. At participant$u$, use the optional-once component expression$e_u=\varepsilon+\sum_{u\in S_v}a_v$. Suppose $\pi:G\to\overline G$is a complementing permutation. Synchronize the expression with the copy in which global letter$a_v$ is read as$a_{\pi(v)}$.

The hypothesis is essential. It applies to the pentagon and to self-complementary Paley graphs, not to the seven-cycle. A one-way edge-to-nonedge permutation can produce an independent diagonal, but without the reverse implication it does not force all second events to block.

FPRD-SH-X04 · exact expression-level calibration

The pentagon twist is reachable in six natural-prefix states

Put $S_i=\{i,i+1\}$ on$\mathbb Z_5$ and give participant $u$ the component expression$e_u=\varepsilon+a_{u-1}+a_u$. The useful component-prefix product states are exactly the matchings of $C_5$: one empty, five single-edge, and five two-edge matchings. Incoming last-signature expansion splits each two-edge matching twice.

Now synchronize this expression with the copy relabelled by$\pi(i)=2i\pmod5$. The ambient square contains $16^2=256$state pairs, but only the initial pair and five one-event pairs are reachable. Their last-signature image is exactly

$$\{(0,0),(1,2),(2,4),(3,1),(4,3)\}.$$

Both coordinate projections have size five, so this set is not a rectangle; it has size five where a product of maximum one-layer packs has size $2\cdot2=4$. Flattening the construction uses ten participants, twenty support incidences, and the raw product$3^{10}=59{,}049$, while its reachable natural prefix automaton still has only six states and five transitions.

This passes the expression-reachability calibration and rules out a rectangle-only theorem. It lists five macro-events, so it is not an asymptotically compact code generator and does not improve a Shannon-capacity bound.

FPRD-SH-T29 · exact reversible compiler

The reversible compiler quotients equal successor sets

A partial deterministic automaton is reversible when, for each input letter, no state has two distinct predecessors bearing that letter. For a two-letter block relation$D\subseteq A^2$, put$D_x=\{y:(x,y)\in D\}$ and$\mathcal R(D)=\{D_x:D_x\ne\varnothing\}$. Use an accepting root $r$, one intermediate state $p_R$ for each distinct successor set, and transitions

$$r\xrightarrow{x}p_{D_x}, \qquad p_R\xrightarrow{y}r\quad(y\in R).$$

For the pentagon permutation code, the fibres are singletons. The lowering therefore has six states, ten transitions, accepts$5^m$ words of length$2m$, and has growth$\sqrt5$. This is the compact regular-language form of the same five-code, consistent with Meiburg's Theorem 14.

The quotient is invisible in the pentagon but necessary for Meiburg's $C_7$ construction. Using the standard vertex alphabet$\{0,1,\ldots,6\}$, its final block is $(6,0)$. Its first coordinates 2 and 4 have the same successor set$\{1,3\}$, while 3 and 5 both have $\{5\}$. Merging them gives the five prefix states$S_0,S_1,S_{24},S_{35},S_6$with pairwise disjoint successor sets$\{2,4\},\{6\},\{1,3\},\{5\},\{0\}$. Together with the root, this is the six-state reversible machine of Theorem 15, with growth$\sqrt{10}$.

Fibre-by-first-coordinate is sufficient but not minimal. Every two-block or longer-block compilation must quotient equal successor residuals before reversibility is assessed.

An independent checker verifies the corrected ten-word code is independent in $C_7^{\boxtimes2}$, and that its six-state quotient has fourteen transitions and is reversible. See the audit certificate.

FPRD-SH-B05 · exact method boundary

Classical automata certificates still factor through finite graph codes

The first sentence is the distinguishability requirement; the second is the limsup defining language growth. Reversible state splitting, feedback, hiding, or an expression compiler may supply a much smaller description and a better structured search, but a classical lower bound always emits ordinary strong-power independent sets at finite lengths. The productive target is therefore succinct generation and verification cost—not a classical capacity certificate that avoids finite slices.

FPRD-SH-C13 · exact expression and reversible audit

The twisted compiler survives exhaustive small tests

FPRD-SH-B06 · corrected semantic boundary

One synchronized macro-event is not a two-letter path block

The reachable compiler in FPRD-SH-X04 and the reversible lowering in FPRD-SH-T29 encode the same classical pentagon code at different semantic layers. In the former, $(i,2i)$ is one composite synchronized event. Over the original alphabet it is a two-event word, represented directly by

$$R_5=(a_0a_0+a_1a_2+a_2a_4+a_3a_1+a_4a_3)^*.$$

The length-$2m$ slice is$\{00,12,24,31,43\}^m$, an independent set of $C_5^{\boxtimes2m}$with size $5^m$. In his 2025 finite-automata construction, Meiburg uses this same starred graph language. Thus both realizations are exact, but reachability of the synchronized six-state macro-event automaton does not determine the natural-prefix count of the direct word expression.

FPRD-SH-X05 · exact direct-expression calibration

The direct block expression has eleven prefix states; six comes after quotienting

Applying the backward recursion of Broda, Maia, Moreira, and Reis to$R_5$ gives exactly

$$\{\varepsilon\}\cup\{R_5a_i:i\in\mathbb Z_5\} \cup\{R_5a_i a_{2i}:i\in\mathbb Z_5\}.$$

These eleven states carry 35 transitions. Merging$\varepsilon$ with the five completed-block states gives the minimal six-state partial DFA$q\xrightarrow{a_i}h_i\xrightarrow{a_{2i}}q$. The quotient is reversible because doubling permutes$\mathbb Z_5$. The natural prefix automaton is not reversible: all six block-boundary states have an $a_i$-edge to the same halfway state.

This six-state quotient is the classical compact block generator; it is distinct from the separately valid six-state synchronized macro-event realization in FPRD-SH-X04.

FPRD-SH-C14 · independent state-space audit

The direct path compiler and its quotient pass an independent audit

The verifier also checks all ten pentagon-code pairs and per-symbol reversibility. All comparisons pass. The earlier 66/81 carrier and 87/191 carrier-controller counts are not retained: the exact source model and verifier for those numbers could not be recovered, so they are not treated as reproduced evidence.

Independent checker · verification output · audit certificate

FPRD-SH-X06 · table-free five-block compiler

The 367-word seven-cycle base code compiles without storing its vectors