SCIENCE@home

Combining decision procedures for the reals

J. Avigad,H. Friedman

Published 2006 in Log. Methods Comput. Sci.

ABSTRACT

We address the general problem of determining the validity of boolean com- binations of equalities and inequalities between real-valued expressions. In particular, we consider methods of establishing such assertions using only restricted forms of distributiv- ity. 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 with symbols 0,1,+, , <, . . . , fa, . . . where for each a 2 Q, fa denotes the function fa(x) = ax. Let Tmult(Q) be the analogous theory for the language with symbols 0,1,×,÷, <, . . . , fa, . . .. We show that although T(Q) = Tadd(Q) ( Tmult(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.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-27 of 27 references · Page 1 of 1

CITED BY

Showing 1-17 of 17 citing papers · Page 1 of 1