Paper Accepted by Inf. Comput.

Our paper titled “On Termination of Polynomial Programs with Equality Conditions” by Yangjia Li (ISCAS), Mingshuai Chen, Liangran Zhao (PKU), Naijun Zhan (PKU), Hui Lu (NAU), Guohua Wu (NTU), and Joost-Pieter Katoen (RWTH Aachen) has been accepted for publication by Information and Computation. This article shows that the set of non-terminating inputs of multi-path polynomial programs with equality conditions is algorithmically computable, which in turn yields the decidability of its termination on a given input. We further present an explicit recursive function, essentially of Ackermannian growth, to compute the maximal length of ascending chains of polynomial ideals under a control function, thereby providing a complete answer to the questions raised by Seidenberg in 1971.