有序实数加法理论新的判定过程与多项式谱
DOI:
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

国家自然科学基金资助项目(69833020);山西省归国留学生基金资助项目(97093)


New Decision Procedures and Polynomial Hierarchy for the Theory of Real Addition with Order
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    推广VolkerWeispfenning关于正的有序实数加法理论的量词消去方法,得到有序实数加法理论的一个量词消去的判定过程.在此基础上构造出一个新的、更为精细的判定方法.并且利用这一结果证明了固定量词长度的子类属于相应计算复杂性的多项式谱.与E.D.Sontag的类似结论比较,从这种简洁的方式可以得到一个较优的结果.这个结果实际上将N.Megiddo的关于正实数理论的结论推广到了一般实数理论.

    Abstract:

    In this paper, a quantifier elimination method for positive real theory with order by Volker Weispfenning is extended to a decision procedure, from which a new and finer decision method for eleminentary theory of real addition with order is given. It is proved that its subclasses of fixed number of quantifiers is in correspondant polynomial hierarchy. The result of this paper is essentially an extension of the claim on positive real theory by N. Megiddo to the whole real theory, which is relatively simply enduced in this paper, and comparably better than the similar result by E.D. Sontag.

    参考文献
    相似文献
    引证文献
引用本文

薛锐.有序实数加法理论新的判定过程与多项式谱.软件学报,2001,12(7):1088-1093

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:1999-10-19
  • 最后修改日期:2000-05-18
  • 录用日期:
  • 在线发布日期:
  • 出版日期:
文章二维码
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号