13 Oct 1996 12:44:59 -0400

Related articles |
---|

Help! Evaluating Many Logical Expressions dinesh@netcom.com (1996-10-10) |

Re: Help! Evaluating Many Logical Expressions ikastan@alumnae.caltech.edu (1996-10-13) |

From: | ikastan@alumnae.caltech.edu (Ilias Kastanas) |

Newsgroups: | comp.compilers,comp.programming |

Date: | 13 Oct 1996 12:44:59 -0400 |

Organization: | Caltech Alumni Association |

Expires: | October 22, 1996 |

References: | 96-10-031 |

Keywords: | optimize |

Dinesh Somkani <dinesh@netcom.com> wrote:

*>I have a requirement to evaluate, real-time, a logical expression made up*

*>of many relational expressions.*

*>*

*>The given expression looks something like this:*

*> A && B && C*

*>or, somewhat more complex, with lots of parentheses and all.*

*>The A, B, C are the relational expressions. The data arrives in*

*>transactions; one transaction can affect only one relational expression.*

Eh, are these Boolean (A, B ... True/False), or are they something

like database queries?

*>I may be able to place some reasonable limit on the number of components*

*>to a logical expression (say, 20).*

*>*

*>The problem is:*

*>(a) how to verify that the given logical expression is meaningful -*

*>detecting truisms like (A && ... && ~A), etc.*

Recognizing a contradiction or a tautology is the archetypal NP-

complete problem; a tractable solution is not likely! Hopefully you

don't need the general case.

*>(b) how to structure the logical expression for evaluation. I have maybe*

*>10000 of these at a time, built using say 100000 components.*

*>(c) structuring - are there ways to simplify a logical expression so*

*>that one keeps doing incremental evaluations (say left to right, or*

*>perhaps in a tree) until there is a conclusive result.*

There are normal forms, but once again reaching them can be slow.

*>(d) Any methods to reduce/normalize the expression, since (once*

*>implemented) speed would become an issue sooner or later.*

Ditto. I think the best chance is to latch onto the particular

features of this problem; what kind of expression, what sort of transacti-

ons, how frequent... Generalities, like: maintain a list of A, B ... and

point to them to assemble expressions, or have A, upon acquisition or

modification of its value, send a message to the (sub)expressions that

contain A, and have them do likewise... probably are not enough.

*>Would appreciate some help - a good reference or a cook book, pointer to*

*>some standard algorithms, or whatever. I need to do this in C/++.*

C++ sounds fine for this... but see if you can find some "logic

engine" too. It would be great if it came as a class library.

Ilias

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.