Synthesis of ranking functions via DNN

doi:10.1007/s00521-021-05763-8

	Synthesis of ranking functions via DNN
	Tan, Wang 1,2; Li, Yi 2
刊名	NEURAL COMPUTING & APPLICATIONS
	2021-02-26
页码	21
关键词	Ranking function DNN Termination Loop programs
ISSN号	0941-0643
DOI	10.1007/s00521-021-05763-8
通讯作者	Li, Yi(liyi@cigit.ac.cn)
英文摘要	We propose a new approach to synthesis of non-polynomial ranking functions for loops via deep neural network(DNN). Firstly, we construct a ranking function template by DNN structure. And then the coefficients of the template can be learned by the train-set we construct to get a candidate ranking function, which is transcendental and non-polynomial because of the existence of sigmoid activation function in the neural network. Finally, the candidate ranking function will be verified to show if it is a real ranking function. Most of the existing methods focus on linear or polynomial ranking functions, and are limited to verification tools, while in this paper we make progress regarding the synthesis of non-polynomial ranking functions and new verification method for candidate ranking functions. The experimental results show us that for some of loops from other work, we can find their ranking functions efficiently. Moreover, for some loops having multi-phase ranking functions obtained by existing methods, our method can directly detect their global ranking functions. Especially, our method can also detect the global ranking functions for some loops with transcendental terms, which cannot be dealt with by existing methods.
资助项目	National Natural Science Foundation of China NNSFC[61572024] ; National Natural Science Foundation of China NNSFC[11771421] ; National Natural Science Foundation of China NNSFC[61103110] ; Natural Science Foundation of Chongqing[cstc2019jcyj-msxmX0638] ; Chinese Academy of Sciences Light of West China program ; Chongqing science and Technology Innovation Guidance Special project[cstc2018jcyj-yszxX0002] ; Chongqing science and Technology Innovation Guidance Special project[cstc2019yszx-jcyjX003] ; National Key Research and Development Project[2020YFA07123000]
WOS研究方向	Computer Science
语种	英语
出版者	SPRINGER LONDON LTD
WOS记录号	WOS:000622272200002
内容类型	期刊论文
源URL	[http://119.78.100.138/handle/2HOD01W0/13017]
专题	中国科学院重庆绿色智能技术研究院
通讯作者	Li, Yi
作者单位	1.Univ Chinese Acad Sci, Beijing 101408, Peoples R China 2.Chinese Acad Sci, Automated Reasoning & Cognit Ctr, Chongqing Inst Green & Intelligent Technol, Chongqing Key Lab Automated Reasoning & Cognit, Chongqing 400714, Peoples R China
推荐引用方式 GB/T 7714	Tan, Wang,Li, Yi. Synthesis of ranking functions via DNN[J]. NEURAL COMPUTING & APPLICATIONS,2021:21.
APA	Tan, Wang,&Li, Yi.(2021).Synthesis of ranking functions via DNN.NEURAL COMPUTING & APPLICATIONS,21.
MLA	Tan, Wang,et al."Synthesis of ranking functions via DNN".NEURAL COMPUTING & APPLICATIONS (2021):21.