Strategies to Fast Evaluation of Expression Trees

Abstract

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.

ÖZ : İfade ağaçları, ifadelerin sözdizimsel yapılarını görselleştirmek için kullanılan araçlardır. Onlar değerlendirmede oldukça yardımcıdırlar, örneğin, karar ağaçları yaygın olarak kullanılanlardandır. Oyun ve oyun teorisi yapay zekada önemli bir alan olup, işletme ve ekonomide çeşitli bağlantılara sahiptir. Kısa devre, kısa yol, ya da diğer bir adıyla tembel değerlendirmeler mantık, donanım tasarımı, programlama, karar verme gibi bilgisayar bilimlerinin çeşitli alanlarında önemli rol oynar. Bu tezde, oyun ağaçlarının uzantıları dahil farklı ağaç modelleri düşünülmüştür. Örneğin, çarpma, toplama(sınırlandırılmış) ve olağan minimum ve maksimum işlemleri ile, en iyi bilinen ve en çok kullanılan bulanık mantık sistemlerinden üç tanesi, çarpma mantığı işlenmiştir. Anahtar kelimeler: ifade ağaçları, oyun ağaçları, formül ağaçları, hızlı hesaplamalar, bulanık mantık, birçok değerli mantık, budama teknikleri, kısa devre hesaplamaları, tembel hesaplamalar.