Established result line

Prefix quotients, synchronization, and event signatures

The program began with the failure of a prefix automaton to be a quotient of a shuffle location automaton. It now includes an exact starred-word classification, sharp synchronized-shuffle boundaries, a Boolean-product quotient-transfer theorem, and an event-signature expansion that measures the state gap between the natural prefix construction and the canonical component product.

These are two different operations. In the Boolean-product automaton, quotienting every component by a left-invariant relation—as defined in A Mesh of Automata—commutes with forming any memoryless product. By contrast, applying the prefix construction to the combined expression can remember which participant set performed the last event. It agrees with the componentwise quotient for every expression exactly when each letter has one participant set and distinct letters' sets overlap.

For ordinary shuffle of two repeated nonempty words, the prefix automaton is a state quotient of the location automaton exactly when both words are powers of the same letter. Even those positive cases fail the stronger left-invariance test: merging states must preserve predecessor blocks as well as forward transitions, and the initial shuffle fork makes those histories incompatible.

Within the unary starred-cycle family, the three synchronized operators of Broda, Machiavelo, Moreira, and Reishave sharply different quotient behavior. Strong synchronization permits only joint moves and gives a left quotient for every pair of cycle lengths. Arbitrary synchronization also permits solo moves: an ordinary quotient then exists exactly when one cycle has length one, and a left quotient only when both do. Weak synchronization restores an ordinary quotient for every pair but never a left quotient. These statements are restricted to the stated unary family.

For a policy $\psi$, a compatibility graph on event signatures gives the exact largest local state split,$\Omega(\psi)=\omega(C_\psi)$. Predicting whether that split reaches a given threshold is NP-complete by a reduction from Karp's three-dimensional matching problem, even with one three-participant support per letter. Total overhead is exactly the collision excess of the signature target sets. For disjoint one-support policies, including pure shuffle, it has a closed finite-size formula: the local clique coefficient is asymptotically sharp, while the finite bound is strict whenever there are at least two active blocks and the product has a noninitial state.

Knuth's exact covering with colors gives an exact sparse representation of compatible event-signature families. In a depth-one graph family, Dancing Links enumerates the natural-prefix overhead without constructing the product, while exact evaluation is #P-complete through a weighted graph-matching identity.

Kupavskii's diversity parameter$\gamma$—the number of supports outside a largest participant star—also parameterizes the exact search. Every compatible family consists of an exceptional matching plus at most one hub support. This gives an$O(|\mathcal F|2^\gamma)$target-intersection-oracle factorization. In the one-shot model, where each component letter occurs at most once, grouping hub supports by their exceptional conflict masks and applying a subset-zeta transform gives an exact$O(|\mathcal F|r\gamma+\gamma2^\gamma)$algorithm without a product automaton.

A largest participant star is only one possible intersecting core. If $\kappa$ supports must be removed to leave any pairwise-intersecting family, the same proofs run in$O(|\mathcal F|2^\kappa)$target-oracle operations and$O(|\mathcal F|r\kappa+\kappa2^\kappa)$one-shot time. Projective-plane lines have$\kappa=0$ but diversity$q^2$, so the gap is unbounded. Thus the intersecting-core parameter can be arbitrarily smaller than diversity. This separation concerns the cost of the exact decomposition, not a new upper bound on diversity itself.

This parameterization is genuinely one-shot. The published DFA trace-counting reductionalready uses an independence graph with one edge, so its vertex-cover number is one; exact unrestricted trace counting is nevertheless $\#\mathrm P$-complete for unary slice length. For a single nonempty Foata step, the cover decomposition does give an exact $O(|\Sigma|\kappa2^\kappa m)$dynamic program. Sequential linearizations, not simultaneous compatibility, create the hard case.

Read the theorems, proofs, and exact audits → · Read the trace-counting boundary →

Established extremal transfer

Kneser independence gives exact zero-overhead thresholds

A Boolean-product policy is a finite set system on its participants. With one distinct letter per$r$-element support, universal zero overhead is exactly independence in the Kneser graph$KG_{n,r}$. The classical Erdős–Ko–Rado theorem gives the overall ceiling $\binom{n-1}{r-1}$when $n\ge2r$. When$n>2r$, equality forces a full star. Below that range, every two supports intersect and the full family is zero-overhead.

If $r\ge2$,$n>2r$, and no participant is common to every support, the sharp Hilton–Milner ceiling drops to$\binom{n-1}{r-1}-\binom{n-r-1}{r-1}+1$. At $n=2r$, the gap disappears: one may choose one support from each complementary pair and still have no common participant.

Above the EKR ceiling, the Kneser spectrum forces an explicit number of disjoint support pairs. Each is already a unit contribution to the depth-one one-shot overhead. A complementary diversity receipt can activate already around a near-star hub. These general receipts are not claimed sharp; stronger supersaturation results apply in restricted parameter ranges.

Diversity is therefore both a structural distance from a star and a valid executable exact-search parameter. It need not be the smallest parameter in the intersecting-core factorization: the optimal such exception count permits any intersecting core and is a minimum vertex cover of the support-disjointness graph. The running-time display assumes that cover is supplied. The exponential dependence is attained by conflict-quotient size and by explicit XCC output, but neither an arithmetic-time lower bound nor optimality among all exact algorithms is claimed.

Read the diversity factorization and intersecting-core correction →

Established exact-search result

Dancing Links gives the exact compiler—and exposes the boundary

The hard core already contains exact cover by three-sets. On a universe of $3k$ participants, choosing $k$ pairwise-disjoint three-participant signatures is an exact cover, so Knuth's Dancing Links applies directly.

The full compatibility rule matches Knuth's 2016 exact covering with colorsexactly. A participant is a nonprimary item and a letter is its color: selected signatures may overlap when the colors agree, and a different color conflicts. Primary on/off selectors make XCC solutions correspond bijectively to compatible signature families.

For graph-edge supports and depth-one components, useful product states are graph matchings and the overhead is$\sum_M(|M|-1)_+$. DLX is therefore an exact product-free enumerator. By Valiant's all-matchings theoremand an explicit isolated-edge reduction, the same identity is #P-complete to evaluate under polynomial-time Turing reductions. The algorithmic gain is sparse, reversible search—not a polynomial-time collapse.

Established policy dictionary and expression calibration

Support tensors reproduce capacity; expressions realize the pentagon twist

Join two signatures when their supports overlap. Cartesian-tensoring supports produces the strong graph product exactly, so their asymptotic packing rate is the Shannon capacity of this overlap graph. This is a policy-level dictionary: a tensor signature is already a strong-power vertex and is not automatically a word or reachable state of a prefix expression.

Perfect overlap graphs have no support-tensor amplification; pure shuffle and full synchronization are the empty and complete boundary cases. The five-cycle has a five-code where one-layer packing predicts four. The expression-level calibration is now separate and exact: an optional-once five-cycle expression has 16 natural-prefix states, while its synchronized doubled-index square has only six reachable states and exposes precisely the five nonrectangular pairs $(i,2i)$. The model is therefore not restricted to rectangular codes.

Over the original alphabet, the direct block expression has eleven natural-prefix states. Its language-preserving quotient is a different six-state partial reversible DFA of growth $\sqrt5$, inside Meiburg's graph-language framework. Reversibility can compress and organize code families, but every classical fixed-length slice is still an ordinary independent set in a strong power. The seven-cycle support policy retains the unknown rate $\Theta(C_7)$; the expression program has not improved that bound. It has now compiled the published five-dimensional 367-code without storing its vectors: a cyclic generator, conflict filter, and three selector bits produce the code, whose best residual DFA has 128 states and 424 transitions.

Read the two compilers, exact counts, and method boundary →

Program boundary

Both outside directions now have proved FPRD translations. Knuth's XCC mechanism, Valiant's counting theorem, and the Erdős–Ko–Rado/Hilton–Milner bounds remain classical sources and are identified as such. The pentagon calibration is now complete. The five-dimensional input for Gao's structured seven-cycle code is now explicit in the path-language model. The table-free compiler reproduces the full private-pair/transversal/$O/H/V$ interface, and Gao's six-step split tree becomes a 204-node typed expression DAG. That DAG has been lowered without expanding its astronomical output: the resulting deterministic path compiler has 192,771 reachable canonical syntax states and 618,415 transitions. A direct two-block check finds 780 canonical syntax states but only 766 distinct residual languages, so the larger count is not asserted to be minimal. This does not prove reversibility or a new capacity bound; the current numerical record is the later Lean-verified two-hundredth-power certificate. The diversity-kernel question is now answered at the one-shot level and conditionally for arbitrary targets. Further work needs an independently motivated application, not another refinement of the same finite kernel.