Nonempty one-Foata-step trace counting is FPT by independence cover

Exact statement

Given an $m$ -state DFA and a supplied vertex cover $B$ of the independence graph with $|B|=\kappa$ , the nonempty one-Foata-step traces touching the DFA language, including their size distribution, can be counted exactly in $O(|\Sigma|\kappa 2^\kappa m)$ time and $O(2^\kappa m)$ auxiliary space.

StatusSelf-contained proof; exhaustive and randomized exact audits pass

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

Context

Removing the cover leaves an independent set in the graph-theoretic sense, so a pairwise-independent Foata step contains at most one outside letter.

Proof or evidence

Subset recurrences collect all DFA states reached by permutations of each cover mask, first without and then with one outside letter.

One-step cover dynamic program →

Verification notes

All 65,536 two-state DFA controls on every four-letter independence graph and 2,500 larger random controls agree with direct permutation enumeration.

Limitations

The theorem counts height-one traces, not arbitrary Foata sequences.
The supplied cover avoids charging for minimum-cover computation.
The simple dynamic program has no confirmed external novelty.

Open work

Use this as the exact scope boundary; any lift to full traces must add a parameter controlling sequential residual amplification.