Note: This list is currently being revised and does not claim to be complete.
Bachelor's thesis
Compact encodings of monotonic Boolean
functions
Author: David Goergen (May 2008)
A Boolean function is monotonic if it can be represented by a combinatorial circuit of AND- and OR-gates. Monotonic Boolean functions play an important role in complexity theory and naturally occur in a number of applications.
The goal of this project is to compute a compact representation for monotonic Boolean functions given as circuits or propositional logic programs, i.e., to find a circuit with a small number of gates which computes the given function. The resulting algorithm shall then be applied to the problem of computing relaxation heuristics for AI planning tasks, and to the problem of line of sight computation in discrete 2D worlds.
