| An Improvement of Herbrand＇s Theorem and Its Application to Model Generation Theorem Proving |
| |
| 引用本文： | 巢宇燕,何立风,中村剛士,石争浩,鈴木賢治,伊藤英則.An Improvement of Herbrand＇s Theorem and Its Application to Model Generation Theorem Proving[J].计算机科学技术学报,2007,22(4):541-553. |
| |
| 作者姓名： | 巢宇燕 何立风 中村剛士 石争浩 鈴木賢治 伊藤英則 |
| |
| 作者单位： | [1]Graduate School of Environment Management, Nagoya Sangyo University, Aichi, Japan [2]College of Mechanical and Electrical Engineering, Shaanxi University of Science and Technology, China [3]Graduate School of Information Science and Technology, Aichi Prefectural University, Aichi, Japan [4]College of Computer and Information Engineering, Shaanxi University of Science and Technology, China [5]Graduate School of Computer Science and Engineering, Nagoya Institute of Technology, Nagoya, Japan [6]Department of Radiology, The University of Chicago, Chicago, U.S.A. |
| |
| 基金项目： | This work was supported partially by T0Y0AKI Scholarship Foundation, Japan. We are deeply grateful to the anonymous referees, who provided a lot of valuable comments that improved this paper greatly. We thank the editor for his/her kind cooperation and help. We also thank E. F. Lanzl for improving the English of this paper. |
| |
| 摘 要： | This paper presents an improvement of Herbrand＇s theorem. We propose a method for specifying a subuniverse of the Herbrand universe of a clause set S for each argument of predicate symbols and function symbols in S. We prove that a clause set S is unsatisfiable if and only if there is a finite unsatisfiable set of ground instances of clauses of S that are derived by only instantiating each variable, which appears as an argument of predicate symbols or function symbols, in S over its corresponding argument＇s sub-universe of the Herbrand universe of S. Because such sub-universes are usually smaller （sometimes considerably） than the Herbrand universe of S, the number of ground instances may decrease considerably in many cases. We present an algorithm for automatically deriving the sub-universes for arguments in a given clause set, and show the correctness of our improvement. Moreover, we introduce an application of our approach to model generation theorem proving for non-range-restricted problems, show the range-restriction transformation algorithm based on our improvement and provide examples on benchmark problems to demonstrate the power of our approach.
|
| 关 键 词： | Herbrand理论 Herbrand全域 子底集 计算机 |
| 修稿时间： | 2006-06-212006-12-21 |
| 本文献已被 维普 等数据库收录！ |
|
