FPRD-LT-D01 · decision problem

The supplied action is the input

Let $A=(Q,\Sigma,\delta)$ be a minimal DFA and let

$$M=\langle\tau_a:a\in\Sigma\rangle\le T_Q.$$

The promise is that $M$ is$\mathcal L$-trivial. Given an explicit transformation $f:Q\to Q$, decide whether $f\in M$. The monoid may contain exponentially many elements even though every generator is listed on only $|Q|$states.

FPRD-LT-L01 · lemma

Membership survives passage to the opposite monoid

This is an algebraic equivalence. It does not yet construct a small transformation action for the opposite monoid.

FPRD-LT-T01 · conditional theorem

A compact faithful action also needs a target code

Suppose one can compute a polynomial-size set$P$, a faithful action$\rho:M^{\mathrm{op}}\hookrightarrow T_P$, the images of all generators, and a partial order on$P$ that makes the action a poDFA. Because the supplied target $f:Q\to Q$need not belong to $M$, also suppose the construction supplies a transformation$t_f\in T_P$ satisfying$t_f=\rho(f)$ when$f\in M$ and$t_f\notin\rho(M)$ otherwise.

The always-available right regular action has one state per element of $M$. It proves that a faithful partially ordered action exists, but not that it is polynomial in the original DFA size.

FPRD-LT-T02 · conditional theorem

Only the target fibre must be faithful

Full faithfulness is stronger than the membership instance needs. Here a poDFA action means that $P$carries a partial order and every generator moves each state only upward or leaves it fixed. Suppose one can compute such a polynomial-size action$\rho:M^{\mathrm{op}}\to T_P$, the generator images, and a transformation$t_f\in T_P$. Since$M$ and$M^{\mathrm{op}}$ have the same underlying elements, require the exact target-code condition

Equality on the right is equality of transformations on$Q$. Thus, when the target is not generated, no element of $M$ may map to $t_f$; the notation does not apply $\rho$ outside its domain.

This remains a conditional route: the target-isolating observation must come from a uniform polynomial-time construction with a proof of the fibre property. Merely guessing a quotient does not make that universal property easy to verify.

FPRD-LT-X01 · exact example

Target isolation can be strictly smaller than faithfulness

Let $M=\{1,a,0\}$ with$a^2=0$. Its principal left ideals are$M\supset\{a,0\}\supset\{0\}$, so it is L-trivial. For target $f=1$, map $1$ to the identity on a two-state chain and map both $a$ and$0$ to its constant top map.

This is a nonfaithful homomorphism into a two-state poDFA monoid, but the fibre over the identity is exactly$\{1\}$. Thus it certifies this target while collapsing the other two monoid elements. Full faithful compression is therefore unnecessary for this single-target decision problem.

Independent multiplication-table and fibre audit · Review certificate

FPRD-LT-C01 · counterexample

Directly reversing the DFA does not work

Take the minimal two-state DFA for “the last letter is$a$.” Letter$a$ sends both states to the final state and $b$ sends both to the other state. Its transition monoid is

$$M=\{1,c_0,c_1\},$$

whose principal left ideals are all distinct. Thus$M$ is L-trivial.

After reversing every transition, one state has both a self-loop and another outgoing edge on the same letter, and the two states lie on a directed cycle. The result is nondeterministic, not partially ordered, and not self-loop deterministic. Transposing the transition matrices has the same defect: it gives relations, not total functions.

FPRD-LT-E01 · finite computation

The four-state pattern did not survive

Exhaustive enumeration of unordered pairs of distinct complete transformations produced the following maxima among L-trivial semiautomata admitting some minimal-DFA final set:

These counts remain an exact baseline, but their apparent$n-1$ pattern is refuted by the five-state result below.

FPRD-LT-T03 · theorem

A binary J-trivial family needs length exactly n

For $n\ge5$, let$Q_n=\{0,1,\ldots,n-1\}$. Define two letters by

with $a$ fixing every other state, and

with $b$ fixing$0,1,n-1$. Use initial state$0$ and sole final state$1$.

This refutes the exact $n-1$conjecture, not polynomial witnesses. A linear lower bound is compatible with Problem 22.19 being in NP.

The hypothesis $n\ge5$ is sharp for this formula: at $n=4$ the same generators reach the target by $bab$, of length three. The one-$a$ lower bound $2n-5$ reaches$n$ only from five states onward.

Independent family and four-state boundary audit · Review certificate

FPRD-LT-E02 · exhaustive computation

The five-state binary maximum is exactly five

Every unordered pair of distinct aperiodic transformations on five states was filtered for accessibility from state$0$, reduced under state relabellings fixing that state and interchange of the letters, closed exactly, tested for L-triviality, and tested against every final set modulo complementation.

The maximum shortest-word diameter is$5$, attained by exactly three generator-pair classes. The smallest extremal uses

generates a 14-element monoid, is minimal with final set$\{1\}$, and first reaches$(4,1,1,1,1)$ by$babab$. A raw labelled pass retained 27,324 minimal L-trivial pairs and 72 extremals, agreeing with the three symmetry classes.

This is an exhaustive finite classification with an independent exact audit of the smallest extremal, not a formal verification or an upper bound for larger automata.

FPRD-LT-X02 · exact example

The extremal target quotient has nine states

The smallest extremal monoid has 14 elements. Regard its left Cayley graph as a DFA with the target$f=(4,1,1,1,1)$ as the sole accepting element. Exact Moore minimization produces nine classes, and the resulting action remains partially ordered.

This is genuine target-specific compression, but it is obtained only after enumerating the 14-element monoid. It therefore does not supply the polynomial construction required to put the general compact-input problem in NP.

FPRD-LT-T04 · theorem

The reversed target fibre has a canonical observer

Let $\eta:\Sigma^*\to M$ be the transition morphism and fix a target$f$. For each$x\in M$, define its left-context profile

The profiles factor through target-relevant fibres. With the right-action convention,

Thus $P_f(x)$ depends only on$\bigl(x^{-1}(y)\bigr)_{y\in\operatorname{im}f}$. This observer may merge arbitrary non-target transformations; it need not preserve the whole opposite-monoid action. The earlier quadratic poDFA transformation bound is unnecessary here because target membership asks for one accepted path, not for another word inducing the same observer transformation.

FPRD-LT-T05 · theorem

The binary counterexample has an exact quadratic observer

For the family in FPRD-LT-T03, put$t=f_n=(n-1,1,\ldots,1)$. Its source transition monoid and canonical target observer have the exact sizes

The source count follows from unique normal forms$b^i$,$b^iab^j$, and$b^iab^jab^k$, together with the single special target. With$L=n-3$, their ranges are

Their counts are$n-2$,$\binom{n-1}{2}$, and$\binom{n-1}{3}$. Pointwise reduction uses

and, on overflow$i+j>L$,

The remaining two-$a$ products reduce by the three capped sums$\min(i+j,L)$,$\min(j+k,L)$, and$\min(i+j+k,L)$. Direct evaluation distinguishes the listed forms, giving$\binom n3+n-1$ elements.

Since $\operatorname{im}t=\{n-1,1\}$, each profile is controlled by$A_x=x^{-1}(n-1)$ and$B_x=x^{-1}(1)$. The nonempty pairs are exactly the following power, interval, and zero types, where$m=n-1$:

Here the power type has$2\le r\le m$; the interval type has $2\le r<s\le m$ except$(r,s)=(2,m)$; and the zero type has$2\le s\le m$. There are $\binom n2-2$ such pairs. All elements with empty$A_x$ form one dead residual. For interval and zero types, every$p\in A$ is realized at state zero by the completing context

For power type use$b^{m-2}a$ for$p=2$,$b^{m-p}ab^{p-2}a$ for$3\le p<m$, and the target itself for $p=m$. These contexts send every other source state into $B$. Consequently distinct sets$A_x$ are extension-distinguishable. This proves the displayed degree exactly.

The result closes this family, not the external complexity problem. It replaces a failed linear conjecture with positive structural evidence: a cubic generated monoid collapses to a quadratic target observer, while the shortest target word remains exactly linear.

FPRD-LT-C02 · exact control

Green height is not target distance

An exhaustive check of all 32,896 unordered generator pairs on four states found 4,473 L-trivial generated monoids. Their maximum left-Cayley height is six, attained by a ten-element monoid, but the largest shortest right-Cayley distance of any target in the entire search is only three.

Ideal-chain height can therefore substantially overestimate the certificate length even inside L-trivial transformation monoids. The exponential Green-height constructions known for unrestricted transformation semigroups do not settle the present problem because they are not shown L-trivial. Likewise, straight-line programs polynomial in an explicitly listed monoid can still be exponential in the degree of the compact transformation input.

This rules out a proxy, not the observer attack. A hard family must force many distinguishable target profiles or genuinely long target geodesics under the L-trivial promise.

FPRD-LT-B01 · open problem

The target-residual degree is the live boundary

Does every positive instance have a word witness of polynomial length in the degree of the supplied L-trivial action? The canonical observer makes one sufficient question exact: is$d_f$ polynomially bounded in$|Q|$ for every target? A positive answer puts membership in NP via the$d_f-1$ path bound. A superpolynomial observer family would refute this particular route, but would not by itself prove superpolynomial target words; another succinct certificate could exist. The binary family now has an exact quadratic observer and therefore settles neither direction.