Incoming labels survive existential quotients

Exact statement

For a letter-labelled NFA $A$ , let $I_A(q)=\{\sigma:\exists p\;(p\xrightarrow{\sigma}q)\}$ . If $\pi:A\twoheadrightarrow B$ is an existential state quotient, then $I_A(q)\subseteq I_B(\pi(q))$ for every state $q$ .

StatusSelf-contained proof; strictly strengthens the loop-spectrum test

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

Context

A shuffle product state can receive differently labelled advances from its two coordinates even when neither advance is recurrent.

Definitions

The incoming spectrum records transition labels, not predecessor identities: $I_A(q)=\{\sigma:\exists p\;(p\xrightarrow{\sigma}q)\}$ .

Proof or evidence

Every edge entering q becomes an edge with the same label entering its quotient block, so no source incoming label can disappear.

Incoming-spectrum theorem →

Verification notes

The original verifier constructs canonical mixed-label locations; an independent review checks all 4,923 ordered word pairs over a three-letter alphabet with total length at most six.

Limitations

The invariant is a necessary condition for a homogeneous target, not a complete quotient criterion for arbitrary NFAs.
No novelty is claimed for the underlying graph observation.

Open work

Test the invariant on broader non-starred shuffle syntax.