AN ANT COLONY ALGORITHM FOR MINIMUM UNSATISFIABLE CORE EXTRACTION  

作　　者：Zhang Jianmin Shen Shengyu Li Sikun 

机构地区：[1]School of Computer Science, National University of Defense Technology, Changsha 410073, China

出　　处：《Journal of Electronics(China)》2008年第5期652-660,共9页电子科学学刊（英文版）

基　　金：the National Natural Science Foundation of China (No.60603088)

摘　　要：Explaining the causes of infeasibility of Boolean formulas has many practical applications in electronic design automation and formal verification of hardware.Furthermore,a minimum explanation of infeasibility that excludes all irrelevant information is generally of interest.A smallest-cardinality unsatisfiable subset called a minimum unsatisfiable core can provide a succinct explanation of infea-sibility and is valuable for applications.However,little attention has been concentrated on extraction of minimum unsatisfiable core.In this paper,the relationship between maximal satisfiability and mini-mum unsatisfiability is presented and proved,then an efficient ant colony algorithm is proposed to derive an exact or nearly exact minimum unsatisfiable core based on the relationship.Finally,ex-perimental results on practical benchmarks compared with the best known approach are reported,and the results show that the ant colony algorithm strongly outperforms the best previous algorithm.Explaining the causes of infeasibility of Boolean formulas has many practical applications in electronic design automation and formal verification of hardware. Furthermore, a minimum explanation of infeasibility that excludes all irrelevant information is generally of interest. A smallest-cardinality unsatisfiable subset called a minimum unsatisfiable core can provide a succinct explanation of infeasibility and is valuable for applications. However, little attention has been concentrated on extraction of minimum unsatisfiable core. In this paper, the relationship between maximal satisfiability and minimum unsatisfiability is presented and proved, then an efficient ant colony algorithm is proposed to derive an exact or nearly exact minimum unsatisfiable core based on the relationship. Finally, experimental results on practical benchmarks compared with the best known approach are reported, and the results show that the ant colony algorithm strongly outperforms the best previous algorithm.

关 键 词：Electronic Design Automation （EDA） Formal verification of hardware Minimum unsatisfiable core Ant colony algorithm Maximal satisfiable subformula 

分 类 号：TN402[电子电信—微电子学与固体电子学]