DISCOVERING NON-TERMINATING INPUTS FOR MULTI-PATH POLYNOMIAL PROGRAMS

LIU Jiang,XU Ming, ZHAN Naijun, ZHAO Hengjun

Journal of Systems Science & Complexity ›› 2014, Vol. 27 ›› Issue (6) : 1286-1304.

PDF(303 KB)
PDF(303 KB)
Journal of Systems Science & Complexity ›› 2014, Vol. 27 ›› Issue (6) : 1286-1304. DOI: 10.1007/s11424-014-2145-6

DISCOVERING NON-TERMINATING INPUTS FOR MULTI-PATH POLYNOMIAL PROGRAMS

Author information +
History +

Abstract

This paper investigates the termination problems of multi-path polynomial programs (MPPs) with equational loop guards. To establish sufficient conditions for termination and nontermination simultaneously, the authors propose the notion of strong/weak non-termination which under/overapproximates non-termination. Based on polynomial ideal theory, the authors show that the set of all strong non-terminating inputs (SNTI) and weak non-terminating inputs (WNTI) both correspond to the real varieties of certain polynomial ideals. Furthermore, the authors prove that the variety of SNTI is computable, and under some sufficient conditions the variety of WNTI is also computable. Then by checking the computed SNTI and WNTI varieties in parallel, termination properties of a considered MPP can be asserted. As a consequence, the authors establish a new framework for termination analysis of MPPs.

Cite this article

Download Citations
LIU Jiang , XU Ming , ZHAN Naijun , ZHAO Hengjun. DISCOVERING NON-TERMINATING INPUTS FOR MULTI-PATH POLYNOMIAL PROGRAMS. Journal of Systems Science and Complexity, 2014, 27(6): 1286-1304 https://doi.org/10.1007/s11424-014-2145-6
PDF(303 KB)

65

Accesses

0

Citation

Detail

Sections
Recommended

/