# Re: Help! Evaluating Many Logical Expressions

## ikastan@alumnae.caltech.edu (Ilias Kastanas)13 Oct 1996 12:44:59 -0400

From comp.compilers

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)
| List of all articles for this month |

 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