期刊文献+

极小不可满足公式的两个多项式时间可判定类 被引量:2

原文传递
导出
摘要 研究命题公式 (合取范式 )的极小不可满足性 .设公式F含有n +k个子句(n是F中所有变元的个数 ) ,其中包括子句x1∨…∨xn 和┐x1∨…∨┐xn,证明了当k≤ 4时 。
机构地区 南京大学数学系
出处 《中国科学(A辑)》 CSCD 1999年第3期198-206,共9页 Science in China(Series A)
基金 国家自然科学基金!(批准号 :197710 45 ) 国家"八六三"计划资助项目
  • 相关文献

同被引文献32

  • 1邵明,李光辉,李晓维.极小布尔不可满足子式的提取算法[J].计算机辅助设计与图形学学报,2004,16(11):1542-1546. 被引量:8
  • 2沈胜宇,李思昆.基于悖论分析和增量求解的快速反例压缩算法[J].软件学报,2006,17(5):1034-1041. 被引量:5
  • 3许道云.极小不可满足公式在多项式归约中的应用[J].软件学报,2006,17(5):1204-1212. 被引量:24
  • 4Chen Z Y, Ding D C. Variable minimal unsatisfiability. In: Theory and Applications of Models of Computation, 2006, LNCS 3959: 262- 273.
  • 5Lau M F, Yu Y T. An extended fault class hierarchy for specification-based testing. ACM T Softw Eng Meth, 2005, 14:247-276.
  • 6Chen Z Y, Xu B W, Nie C H. A detectability analysis of fault classes for Boolean specifications. In: 23rd Annual ACM Symposium on Applied Computing, 2008. 390-394.
  • 7Ravi K, Somenzi F. Minimal assignments for bounded model checking. In: 10th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, 2004. 31-45.
  • 8Papadimitriou C H, Yannakakis M. The complexity of facets (and some facets of complexity). J Comput Syst Sci, 1984, 28:244-259.
  • 9Kleine B H, Lettmann T. Propositional Logic: Deduction and Algorithms. London: Cambridge University Press, 1999.
  • 10Umans C. The minimum equivalent DNF problem and shortest implicants. J Comput Syst Sci, 2001, 53:597-611.

引证文献2

二级引证文献9

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部