formal derivation of a high-trustworthy generic algorithmic program for solving a class of path problems

	formal derivation of a high-trustworthy generic algorithmic program for solving a class of path problems
	Wang Changjing; Xue Jinyun
	2009
会议名称	3rd International Frontiers of Algorithmics Workshop, FAW 2009
会议录名称	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
会议日期	37427
会议地点	Hefei, China
出版地	Germany
ISSN	3029743
ISBN	3642022693
部门归属	(1) Key Laboratory for High-Performance Computing Technology, Jiangxi Normal University, Nanchang 330022, Thailand; (2) Institute of Software, Chinese Academy of Sciences, Beijing 100190, China; (3) Graduate University, Chinese Academy of Sciences, Beijing 100190, China
摘要	Recently high-trustworthy software has been proposed and advocated by many academic and engineering communities. High-trustworthy algorithm is core to high-trustworthy software. In this paper, using PAR method we derive formally a high-trustworthy generic algorithmic program for solving general single-source path problems. Common characteristics of these path problems can be abstracted into an algebra structure-dioid. Some typical graph algorithms, such as Bellman-Ford single-source shortest path algorithm, Reachability problem algorithm, and Bottleneck problem algorithm, etc. are all instances of the generic algorithmic program. Our approach mainly employs formal derivation technology and generic technology. Main contribution is combining the two techniques into a systemic approach, which aims to develop high-trustworthy generic algorithmic program for solving general problems. According to our approach, the correctness, reliability, safety and development efficiency of algorithmic programs are greatly improved. It is expected to be a promising approach to develop high-trustworthy generic algorithmic program. © 2009 Springer Berlin Heidelberg.
关键词	Algorithms Computer Software
内容类型	会议论文
URI标识	http://ir.iscas.ac.cn/handle/311060/8418
专题	基础软件与系统重点实验室
推荐引用方式 GB/T 7714	Wang Changjing,Xue Jinyun. formal derivation of a high-trustworthy generic algorithmic program for solving a class of path problems[C]. Germany,2009.