The analysis developed by L\"uscher and Schaefer of the Hybrid Monte Carlo (HMC) algorithm is extended to include Fourier acceleration. We show for the $\phi^4$ theory that Fourier acceleration substantially changes the structure of the theory for both the Langevin and HMC algorithms. When expanded in perturbation theory, each five-dimensional auto-correlation function of the fields $\phi(x_i, t_i)$, $1\le i \le N$, corresponding to a specific 4-dimensional Feynman graph separates into two factors: one depending on the Monte-Carlo evolution times $t_i$ and the second depending on the space-time positions $x_i$. This separation implies that only auto-correlation times at the lattice scale appear, eliminating critical slowing down in perturbation theory.