Institutional Repository
| formal derivation of a high-trustworthy generic algorithmic program for solving a class of path problems | |
| Wang Changjing; Xue Jinyun | |
| 2009 | |
| Conference Name | 3rd International Frontiers of Algorithmics Workshop, FAW 2009 |
| Source | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
| Conference Date | 37427 |
| Conference Place | Hefei, China |
| Publish Place | Germany |
| ISSN | 3029743 |
| ISBN | 3642022693 |
| Department | (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 |
| English Abstract | 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. |
| Keyword | Algorithms Computer Software |
| Content Type | 会议论文 |
| URI | http://ir.iscas.ac.cn/handle/311060/8418 |
| Collection | 基础软件与系统重点实验室 |
| Recommended Citation 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. |
| Files in This Item: | There are no files associated with this item. | |||||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment