Time-optimal short-circuit evaluation of Boolean expressions (Q1115174)

Das Verfahren der Berechnung Boolscher Ausdrücke duch ``short- circuiting'' wird durch Einbeziehung der Möglichkeit, durch Umordnung unter Verwendung der kommutativen und assoziativen Gesetze für ``und'' und ``oder'' zeitoptimale Berechnung zu erzielen, weiterentwickelt. Dabei wird die mittlere Zeit und die wahr-/falsch-\(Wahrscheinlichkeit\) abgeschätzt und unter Benutzung des Verfahrens der dynamischen Optimierung die mittlere Zeit minimiert. Im Mittelpunkt steht dabei das Minimierungstheorem, das im Anhang bewiesen wird. Anwendungen finden sich sowohl in den Programmiersprachen und ihren Compilern als auch in den Datenbanksprachen. Ein ausführlich behandeltes Beispiel zeigt den Minimierungseffekt.