Let ${\left(F_n\right)}_{n\in \mathbb{N}}$ be a sequence of non-decreasing functions from $[0,+\infty )$ into $[0,+\infty )$. Under some suitable hypotheses of ${\left(F_n\right)}_{n\in \mathbb{N}}$, we will prove that if $g\in L^p\left({ℝ}^N\right)$, $1<p<+\infty$, satisfies ${lim\; inf}_{n\to \infty }{\int }_{{ℝ}^N}{\int }_{{ℝ}^N}{F}_n{\left(\right|g\left(x\right)-g\left(y\right)\left|\right)/|x-y|}^{N+p}dxdy<+\infty$, then $g\in W^{1,p}\left({ℝ}^N\right)$ and moreover ${lim}_{n\to \infty }{\int }_{{ℝ}^N}{\int }_{{ℝ}^N}{F}_n{\left(\right|g\left(x\right)-g\left(y\right)\left|\right)/|x-y|}^{N+p}dxdy=K_{N,p}{\int }_{{ℝ}^N}{\left|\nabla g\left(x\right)\right|}^{p}dx$, where $K_{N,p}$ is a positive constant depending only on $N$ and $p$. This extends some results in J. Bourgain and H-M. Nguyen [A new characterization of Sobolev spaces, C. R. Acad Sci. Paris, Ser. I 343 (2006) 75-80] and H-M. Nguyen [Some new characterizations of Sobolev spaces, J. Funct. Anal. 237 (2006) 689-720]. We also present some partial results...