Configuration Identity as a Formal Parameter in Deterministic State Counting

Standard models of deterministic computation count configurations as distinct states whenever their concrete encodings differ. The practice is everywhere and is rarely isolated as a formal choice, even though arguments about reachable state-space size and traversal cost are stated relative to it.

This paper treats configuration identity as a parameter. Deterministic transition systems are equipped with an equivalence relation on configurations and a canonical representative map, and computation is then defined over canonical states.

Three results follow. Under acceptance-preserving and successor-compatible equivalence, quotient dynamics are well defined and deterministic. Finite path projection and lifting preserve acceptance behaviour between concrete and canonical computation. And if successor generation and canonicalisation are effectively computable and the reachable canonical state space is finite, or polynomially bounded on an input family, the resulting canonical traversal is finite, or polynomial-time, respectively.

What it is not. It is a framework for model-relative state counting, not a bound on any particular problem. Problem-specific upper bounds still require separate proofs that the equivalence and the canonical map exist and are computationally accessible.