首页    期刊浏览 2025年02月20日 星期四
登录注册

文章基本信息

  • 标题:Combining Decision Procedures for the Reals
  • 本地全文:下载
  • 作者:Jeremy Avigad ; Harvey Friedman
  • 期刊名称:Logical Methods in Computer Science
  • 印刷版ISSN:1860-5974
  • 电子版ISSN:1860-5974
  • 出版年度:2006
  • 卷号:2
  • 期号:04
  • DOI:10.2168/LMCS-2(4:4)2006
  • 出版社:Technical University of Braunschweig
  • 摘要:

    We address the general problem of determining the validity of boolean combinations of equalities and inequalities between real-valued expressions. In particular, we consider methods of establishing such assertions using only restricted forms of distributivity. At the same time, we explore ways in which "local" decision or heuristic procedures for fragments of the theory of the reals can be amalgamated into global ones.

    Let Tadd[Q] be the first-order theory of the real numbers in the language of ordered groups, with negation, a constant 1, and function symbols for multiplication by rational constants. Let Tmult[Q] be the analogous theory for the multiplicative structure, and let T[Q] be the union of the two. We show that although T[Q] is undecidable, the universal fragment of T[Q] is decidable. We also show that terms of T[Q]can fruitfully be put in a normal form. We prove analogous results for theories in which Q is replaced, more generally, by suitable subfields F of the reals. Finally, we consider practical methods of establishing quantifier-free validities that approximate our (impractical) decidability results

  • 关键词:Decision Procedures;Real Numbers
国家哲学社会科学文献中心版权所有