SVMRanker: A General Termination Analysis Framework of Loop Programs via SVM
Deciding termination of programs is probably the most famous problem in computer science. Synthesizing ranking functions for programs is a standard way to prove termination of programs. Currently, specific synthesis algorithms have to be developed for each specific type of programs. For instance, the synthesis of ranking functions for programs with linear variables updates is usually based on linear programming techniques and the like, while for programs with polynomial updates, it usually relies on semi-definite programming and the like. The same also applies to the synthesis of different types of ranking functions needed for proving program termination. Each time faced with a new type of programs and a new type of ranking functions, researchers have to spend a considerable amount of effort to develop specialized synthesis algorithms. In this paper, to save this extra effort, we present \textsc{SVMRanker}, a general framework for proving termination of programs, which is able to synthesize different types of ranking functions for programs with both linear and polynomial updates, based on Support-Vector Machines (SVM). We compare \textsc{SVMRanker} with the state-of-the-art tool \textsc{LassoRanker} on standard benchmarks. Empirical results show that \textsc{SVMRanker} is comparable with \textsc{LassoRanker} on programs with linear updates and can manage more programs with polynomial updates, making \textsc{SVMRanker} a valid complement to \textsc{LassoRanker} in proving program termination.
Fri 13 NovDisplayed time zone: (UTC) Coordinated Universal Time change
01:30 - 02:00 | |||
01:30 2mTalk | AlloyMC: Alloy Meets Model Counting Tool Demos Jiayi Yang University of Texas at Austin, USA, Wenxi Wang University of Texas at Austin, USA, Darko Marinov University of Illinois at Urbana-Champaign, Sarfraz Khurshid University of Texas at Austin DOI | ||
01:32 2mTalk | HISyn: Human Learning-Inspired Natural Language Programming Research Papers Zifan Nan North Carolina State University, USA, Hui Guan North Carolina State University, USA, Xipeng Shen North Carolina State University, USA DOI | ||
01:35 1mTalk | Inductive Program Synthesis over Noisy Data Research Papers Shivam Handa Massachusetts Institute of Technology, USA, Martin C. Rinard Massachusetts Institute of Technology, USA DOI | ||
01:37 1mTalk | MCBAT: A Practical Tool for Model Counting Constraints on Bounded Integer Arrays Tool Demos Abtin Molavi Harvey Mudd College, USA, Mara Downing Harvey Mudd College, USA, Tommy Schneider Harvey Mudd College, USA, Lucas Bang Harvey Mudd College DOI | ||
01:39 1mTalk | SVMRanker: A General Termination Analysis Framework of Loop Programs via SVM Tool Demos Xie Li , Yi Li Nanyang Technological University, Yong Li Institute of Software, Chinese Academy of Sciences, Xuechao Sun Institute of Software at Chinese Academy of Sciences, China, Andrea Turrini State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Lijun Zhang Institute of Software, Chinese Academy of Sciences DOI | ||
01:41 19mTalk | Conversations on SAT and Synthesis Paper Presentations Abtin Molavi Harvey Mudd College, USA, Jiayi Yang University of Texas at Austin, USA, Lucas Bang Harvey Mudd College, Xie Li , Zifan Nan North Carolina State University, USA, Shivam Handa Massachusetts Institute of Technology, USA, M: Abhik Roychoudhury National University of Singapore, Singapore |