The support cover is a concurrency parameter

A concurrent alphabet consists of an alphabet$\Sigma$ and a symmetric, irreflexive independence relation$\mathbb I$. Adjacent independent letters may commute. Their equivalence classes are Mazurkiewicz traces.

The full counting problem also receives a length$n$, encoded in unary, and asks how many traces contain at least one accepted word of that length. The unary convention is part of the published complexity statement, not a harmless implementation detail.

View $\mathbb I$ as an undirected graph and let

be its minimum vertex-cover number. If$B$ is a cover, then$C=\Sigma\setminus B$contains no independent pair. Consequently a simultaneous independent step contains an arbitrary clique from$B$ and at most one letter from $C$.

FPRD-SH-B11 · sharp negative boundary

Full trace counting is hard at cover number one

De Colnet, Meel, and Mathur prove exact DFA trace counting$\#\mathrm P$-hard in their Theorem 3.2, by a parsimonious reduction from$\#\mathrm{DNF}$. Their Theorem 3.1 separately proves membership in$\#\mathrm P$. The reduction uses the fixed alphabet

The reduction represents term choice by the position of one$b$ among repeated$a$s:

These are presentations of one trace, while the DFA uses the position to test one DNF term. A trace touches the language when at least one presentation selects a satisfied term. Choosing$B=\{b\}$ shows more: every accepted word contains exactly one occurrence of the only cover letter.

At $\kappa=0$ no letters commute, traces are words, and length-slice counting for a DFA is polynomial when the length is unary. The exact boundary therefore jumps from polynomial at zero to $\#\mathrm P$-complete at one.

FPRD-SH-T34 · exact height-one algorithm

The cover works for one nonempty Foata step

In the Cartier–Foata view of traces, one nonempty height-one step is a clique$S$ of the independence graph: its letters occur once, are pairwise independent, and all permutations of $S$ form one trace. The trace touches a DFA language when some permutation is accepted.

Every clique is uniquely either$N\subseteq B$ or$N\cup\{c\}$ for one$c\in C$. For$N\subseteq B$, let$R_0(N)$ be the DFA states reached by all permutations of$N$. Then

For a fixed core letter$c$, the corresponding sets satisfy

Splitting a permutation by its final letter proves the recurrences. A candidate touches the language exactly when its reachable-state set meets the final states. The recurrence may be evaluated for every mask, but only clique masks—and, for$N\cup\{c\}$, masks compatible with $c$—are counted. There are$2^\kappa$ cover masks, and the core letters are processed one at a time.

FPRD-SH-C19 · exact computational audit

Kernel and direct permutation counts agree

The exact audit compares the kernel dynamic program with direct subset and permutation enumeration. Two complete runs produced byte-identical output.

Audit program · canonical output · review certificate

The missing resource is sequential presentation width

The cover number bounds simultaneous compatibility among action types. It does not bound the number of positions an exceptional occurrence can occupy among repeated dependent actions, or the number of DFA residual states exposed by those positions. The hard construction has only one exceptional occurrence, but it exposes an unbounded term-selection orbit.

Any useful refinement must therefore control a presentation-sensitive quantity—such as the number of distinct DFA residuals realized by the linearizations of a trace prefix—in addition to the independence cover. Another parameter depending only on the fixed alphabet graph cannot change this hardness boundary.