Signature-Based Method of Deciding Program Termination

Yaohui Li (), Yuqing Song and Zhifeng Wu
Additional contact information
Yaohui Li: Tianjin University of Technology and Education, Department of Computer Science
Yuqing Song: Tianjin University of Technology and Education, Department of Computer Science
Zhifeng Wu: Tianjin University of Technology and Education, Department of Computer Science

A chapter in Computer Mathematics, 2014, pp 297-310 from Springer

Abstract: Abstract We present a method based on the discriminant sequence and Gröbner bases to verify the termination of a class of linear program. This method relates the program termination to the existence of real zeros of polynomial system with constraint conditions. To avoid the wrong determination due to approximate computation, we use Gröbner bases and revised sign list to count sign changes of characteristic polynomial of a trace matrix. This method need not solve the equations of polynomial system but count the number of real zeros which satisfy the constraint condition by using symbolic computation. The number of real zeros of polynomial in the linear program can always be computed correctly. Therefore, the termination of the program can be decided accurately.

Keywords: Linear loop program; Termination; Program verification; Gröbner basis; Sturm sequence (search for similar items in EconPapers)
Date: 2014
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-662-43799-5_22

Ordering information: This item can be ordered from
http://www.springer.com/9783662437995

DOI: 10.1007/978-3-662-43799-5_22

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().