Decomposable Theories

Details Decomposable Theories Decomposable Theories

2006-07-13

arxiv.org/abs/cs/0607065v1

Computer Science

Logic in Computer Science

Scientific paper

We present in this paper a general algorithm for solving first-order formulas in particular theories called "decomposable theories". First of all, using special quantifiers, we give a formal characterization of decomposable theories and show some of their properties. Then, we present a general algorithm for solving first-order formulas in any decomposable theory "T". The algorithm is given in the form of five rewriting rules. It transforms a first-order formula "P", which can possibly contain free variables, into a conjunction "Q" of solved formulas easily transformable into a Boolean combination of existentially quantified conjunctions of atomic formulas. In particular, if "P" has no free variables then "Q" is either the formula "true" or "false". The correctness of our algorithm proves the completeness of the decomposable theories. Finally, we show that the theory "Tr" of finite or infinite trees is a decomposable theory and give some benchmarks realized by an implementation of our algorithm, solving formulas on two-partner games in "Tr" with more than 160 nested alternated quantifiers.

Affiliated with

Also associated with

No associations

Rating

Decomposable Theories 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 Decomposable Theories, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Decomposable Theories will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-480479