Combining decision procedures for the reals

Computer Science – Logic in Computer Science

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

Will appear in Logical Methods in Computer Science

Scientific paper

10.2168/LMCS-2(4:4)2006

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.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Combining decision procedures for the reals does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Combining decision procedures for the reals, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Combining decision procedures for the reals will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-353641

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.