Occurrence-minimal shuffle counterexample

Exact statement

For distinct letters $a\ne b$ , the three-state prefix automaton of $a^*\amalg b^*$ is not a quotient of its four-state location automaton. The expression has exactly two letter occurrences, the minimum among shuffle expressions whose two operands both contain a letter.

StatusSelf-contained proof and exact verifier reproduction

External reviewNo documented external or specialist review of these FPRD results is recorded.

Context

Broda et al. (2023), Example 13, gives a four-letter-occurrence counterexample; the same local obstruction appears with only two occurrences.

Hypotheses and scope

Both shuffle operands contain a letter; a and b are distinct.

Proof or evidence

The terminal product location has both an a-loop and a b-loop. A nondegenerate shuffle needs at least one letter occurrence in each operand, so two occurrences are minimal.

Minimal counterexample and transition tables →

Verification notes

All states and transitions were reconstructed, and all 12 surjective initial-preserving maps from the four source states to the three target states were rejected by an independent checker.

Limitations

Occurrence minimality is relative to shuffle syntax in which both operands contain a letter.
No literature-priority claim is made.

Open work

Retain as the sharp occurrence-count boundary; make no literature-priority claim.