FPRD LabShare an approach

← Claims

Computational finding · exhaustive classification

FPRD-LT-E02

Five-state binary L-trivial diameter is exactly five

Exact statement

Among binary five-state semiautomata with L-trivial transition monoid that admit a minimal-DFA final set, exhaustive enumeration finds maximum shortest-word diameter 5. Up to state relabelling fixing the initial state and interchange of the two letters, there are 1,148 retained generator-pair classes and exactly three extremal classes.

StatusExact finite computation with an independent extremal audit
External reviewNo documented external or specialist review of this FPRD result is recorded.

Context

This is the first state size at which the previously observed n-minus-one pattern fails.

Hypotheses and scope

  • The initial state is fixed as 0; every accessible minimal DFA is represented after relabelling.
  • Distinct generators are enumerated unordered; equal generators are unary and have diameter at most four.
  • Final sets are tested modulo complementation.

Proof or evidence

From 839,160 unordered pairs of aperiodic transformations, 210,888 are accessible from state 0. Symmetry reduction retains 8,833 pairs; 1,238 generate L-trivial monoids and 1,148 admit a minimal final set. Their maximum diameter is five, attained by three generator-pair classes. The raw labelled pass contains 27,324 qualifying pairs and 72 extremals.

Five-state exhaustive classification →

Verification notes

L-triviality is tested as singleton SCCs of the left Cayley graph; distances come from exact BFS in T_5. A separate tuple/set implementation checks the smallest 14-element extremal, all principal left ideals, minimality, and the length-five target witness babab.

Limitations

  • This is a finite computational classification, not a formal verification or an asymptotic upper bound.
  • No claim is made about larger alphabets or the general NP-versus-PSPACE question.

Open work

Use the explicit family in FPRD-LT-T03 as the corrected lower-bound baseline; do not infer a general upper bound from five states.