Strategies to Fast Evaluation of Expression Trees

Expression trees are well-known tools to visualize the syntactical structure of the expressions. They are helpful also in evaluations, e.g., decision trees are widely used. Games and game theory form an important field in Artificial Intelligence and it has several connections to Business and Economy. Short circuit, short cut, or by other name, lazy evaluations play important roles in various fields of computer science including logic, hardware design, programming, decision making. In this thesis, different types of trees are considered including extensions of game trees using operations, e.g., multiplication, (constrained) addition and the usual minimum and maximum, and three of the best known and used fuzzy logic systems, (Gödel, Lukasiewicz, and product logics). The evaluation of lots of formulae can be speeded up by various pruning techniques by discovering which remaining part of the formulae has no influence on the final result for various reasons. The presented techniques can be seen as generalizations of short circuit evaluations in Boolean logic and also of alpha-beta pruning of game trees. Simulation results show the efficiency of the presented techniques. Keywords: expression trees, game trees, formula trees, fast evaluation, fuzzy logic, many valued logic, pruning techniques, short circuit evaluation, lazy evaluations.