Computing and Information Systems - Research Publications

Permanent URI for this collection

Now showing 1 - 2 of 2

Un-kleene boolean equation solving

Herlihy, B ; Schachte, P ; Sondergaard, H (WORLD SCIENTIFIC PUBL CO PTE LTD, 2007-04)

We present a new method for finding closed forms of recursive Boolean function definitions. Traditionally, these closed forms are found by Kleene iteration: iterative approximation until a fixed point is reached. Conceptually, our new method replaces each k-ary function by 2k Boolean constants defined by mutual recursion. The introduction of an exponential number of constants is mitigated by the simplicity of their definitions and by the use of a novel variant of ROBDDs to avoid repeated computation. Experiments suggest that this approach is significantly faster than Kleene iteration for examples that require many Kleene iteration steps.
Information loss in knowledge compilation: A comparison of Boolean envelopes

Schachte, P ; Sondergaard, H ; Whiting, L ; Henshall, K (ELSEVIER SCIENCE BV, 2010-06)