For a wide class of polynomially nonlinear systems of partial differential equations we suggest an algorithmic approach to the s(trong)consistency analysis of their finite difference approximations on Cartesian grids. First we apply the differential Thomas decomposition to the input system, resulting in a partition of the solution set. We consider the output simple subsystem that contains a solution of interest. Then, for this subsystem, we suggest an algorithm for verification of s-consistency for its finite difference approximation. For this purpose we develop a difference analogue of the differential Thomas decomposition, both of which jointly allow to verify the s-consistency of the approximation. As an application of our approach, we show how to produce s-consistent difference approximations to the incompressible Navier-Stokes equations including the pressure Poisson equation. © 2019 Association for Computing Machinery.