thus $\tilde{m}_i\prec\tilde{m}_j$, which is contrary to $j<i$.

Note that $\deg(m_j^\prime)=f(j)-\beta< f(j)-\alpha<f(i)-\alpha=\deg(m_j^\prime)$. Then we can find some monomial $m'\in\mathcal[{\pmb{x}}]$ such that $\deg(m')=f(j)-\alpha$, and $m'$ is simultaneously a multiple of $m_j^\prime$ and a factor of $m_i^\prime$. Put $\tilde{m}=m'x_{d+1}^\alpha\in\mathcal{M}[{\pmb{x}},x_{d+1}]$, then $\deg(\tilde{m})=f(j)=\deg(\tilde{m}_j)$ and $\tilde{m}\prec \tilde{m}_j$. So $\tilde{m}$ is also in the sequence $\tilde{m}_1,\cdots,\tilde{m}_n$. However, $\tilde{m}_i$ is a multiple of $\tilde{m}$ and thus we find contradiction. $\Box$

$\Omega(d,f,f(1))=N\leq L(d,f)$ follows immediately from this result. Therefore, we obtain the following theorem.

\[thm:bound\] $L(d,f)=\Omega(d,f,f(1))$.

\[exm:incorrect\] For $d=2 ,f(i)=1+i$, the monomial set of the longest monomial ascending chain is $$\{ m_1,m_2,...,m_{11}\}=\{x^2,xy^2,xy,x,y^6,y^5,y^4,y^3,y^2,y,1\},$$ and $L(2,f)=11$.

However, according to Moreno-Socías’s approach [@GMS92], the monomial set is $$\{x^2,xy^2,y^4,y^3,xy,y^2,x,y,1\}$$ and thus $L(2,f)=9$, which is obviously wrong.

More generally, it can be proved that for $f(i)=ai+b$, $$\label{equ:linear-length}L(d,f)=\frac{1}{a}((a+1)\uparrow^{d-2}(a+b+1)-a-b-2), a>0.$$ Here, $\uparrow$ is used to define the Ackermann’s function same as in [@GMS92]. In fact, the length of the $f$-generating sequence defined by (\[equ:hatm\]) has been correctly computed in [@GMS92] by $$N=\frac{1}{a}((a+1)\uparrow^{d-1}(a+b+1)-a-b-2).$$ Note that $\Omega(d-1,f,f(1))=N$, then (\[equ:linear-length\]) follows immediately from this result and Theorem \[thm:bound\].

Termination of multi-path polynomial programs with equality guards {#sec:MPP}
==================================================================

Multi-path polynomial programs
------------------------------

The polynomial programs considered in this paper are formally defined as follows:

\[def:mpp\] A multi-path polynomial program 