期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

MAX^+(1)和MAX^+(2)公式的分裂特征

Splitting Characteristics of MAX^+(1) and MAX^+(2)
下载PDF
导出
摘要 改名技术在简化一些难例公式的消解证明和构造高效的可满足算法方面有重要意义。MAX+公式是MU公式中的一个重要子类,该类公式可以通过递归的方式产生。为研究MAX+公式改名问题的复杂性,对MAX+(1)和MAX+(2)公式的分裂问题进行了分析,得到了一些关于这两类公式的若干分裂特征,对进一步研究MAX+公式的改名问题有较大的现实意义。 Renamings technique has played a significant role in the construction of efficent satisfiability algorithms and simplifying resolution proofs of some hard formulas.A subclass MAX＋ formulas in minimal unsatisfiable formulas can be constructed recursively.In this article,the splitting characteristics of MAX＋（1） and MAX＋（2） formulas is analyzed and shown to research the renaming problem of MAX＋ formulas further.
作者 姚雷博 布挺 董红政 段晓明
机构地区 洛阳理工学院
出处 《计算机与数字工程》 2010年第11期45-47,51,共4页 Computer & Digital Engineering
关键词 MAX^+(1) MAX^+(2) 分裂 特征 MAX^＋（1） MAX^＋（2） splitting characteristics
分类号 TP301.6 [自动化与计算机技术—计算机系统结构]
  • 相关文献

参考文献8

  • 1Kleine Buning H. On subclasses of minimal unsatisfiable formulas[J]. Discrete Applied Mathematics, 2000, 107(1-3): 83498.
  • 2C.H. Papadimitriou, D. Wolfe. The complexity of facets resolved [J]. Journal of Computer and System Sciences, 1988,37 : 2-13.
  • 3Krishnamurthy B. Short proofs for tricky formulas[J]. Acta Informatica, 1985,22 (3) : 253-275.
  • 4Urquhart A. The symmetry rule in propositional logic [J]. Discrete Applied Mathematics, 1999, 96-97 (1) :177-193.
  • 5Xu DY. On the complexity of renamings and homomorphisms for minimal unsatisfiable formulas[Ph, D, Thesis]. Nanjing: Nanjing University,2002.
  • 6Kleine B ning H, Xu DY. The complexity of homomorphisms and renamings for minimal unsatisfiable formulas[J]. Annals of Mathematics and Artificial Intelligence,2005,43(1-4) :113-127.
  • 7许道云,董改芳,王健.MAX(1)和MARG(1)中公式改名的复杂性(英文)[J].软件学报,2006,17(7):1517-1526. 被引量：3
  • 8CHEN Qing-yan, XU Dao-yun. Polynomial Decidability of Renaming for Formulas in MAX^+ (k)[J]. Journal of Guizhou University( Natural Sciences), 2005,22 ( 2 ) : 184-192.

二级参考文献13

  • 1Krishnamurthy B.Short proofs for tricky formulas.Acta Informatica,1985,22(3):253-275.
  • 2Urquhart A.The symmetry rule in propositional logic.Discrete Applied Mathematics,1999,96-97(1):177-193.
  • 3Xu DY.On the complexity of renamings and homomorphisms for minimal unsatisfiable formulas[Ph.D.Thesis].Nanjing:Nanjing University,2002.
  • 4Papadimitriou CH,Wolfe D.The complexity of facets resolved.Journal of Computer and System Sciences,1988,37(1):2-13.
  • 5Aharoni R.Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas.Journal of Combinatorial Theory,1996,43(A):196-204.
  • 6Davydov G,Davydova I,Kleine Büning H.An efficient algorithm for the minimal unsatisfiability problem for a subclass of CNF.Annals of Mathematics and Artificial Intelligence,1998,23(3-4):229-245.
  • 7Fleischner H,Kullmann O,Szeider S.Polynomial-Time recognition of minimal unsatisfiable formulas with fixed clause-variable difference.Theoretical Computer Science,2002,289(1):503-516.
  • 8Kleine Büning H,Zhao XS.Polynomial time algorithms for computing a represent(a)tion for minimal unsatisfiable formulas with fixed deficiency.Information Processing Letters,2002,84(3):147-151.
  • 9K(o)bler J,Sch(o)ning U,Toran J.The Graph Isomorphism Problem:Its Structural Complexity.Birkh(a)user Verlag,1993.
  • 10Kleine Büning N,Xu DY.The complexity of homomorphisms and renamings for minimal unsatisfiable formulas.Annals of Mathematics and Artificial Intelligence,2005,43(1-4):113-127.

共引文献2

计算机与数字工程
2010年 第11期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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