a guard will result in the termination problem undecidable.

The rest of the paper is organized as follows. In Section \[sec:nutshell\], we give an overview of our approach by a running example. In Section \[sec:pre\], some concepts and results on computational algebraic geometry are reviewed. Section \[sec:bound\] is devoted to computing the upper bound on the length of a descending chain of algebraic sets. In Section \[sec:MPP\], we introduce the model of MPPs with equality guards. In Section \[sec:Deci\], we prove the decidability of the termination problem of the MPPs by proposing an algorithm to compute the set of non-terminating inputs. Section \[sec:pgc\] extends the decidability result to polynomial guarded commands with equality guards. Section \[sec:case\] reports some experimental results with our method. A conclusion is drawn in Section \[sec:conc\].

A running example {#sec:nutshell}
=================

Consider the following polynomial program (denoted by `running`):

\[exm:running\] $$\begin{split}
&(x,y) \coloneqq (x_0,y_0);\\
&\textsc{ while}\ (x+y=0)\ \textsc{do}\\
&\quad \textsc{if ? then}\ (x,y) \coloneqq (y^2,2x+y);\\
&\quad \textsc{else}\ (x,y) \coloneqq (2x^2+y-1,x+2y+1);\\
&\textsc{ end \ while}
\end{split}$$ Here “<span style="font-variant:small-caps;">?</span>” means that the condition has been ignored by abstraction of the program, and thus in each iteration these two assignments are *nondeterministically* chosen. Our problem is to decide 