2009 Computing: The Australasian Theory Symposium

held in Wellington, New Zealand January 20-23 2009.

Guest Editors: Rod Downey, Victoria University of Wellington, NZ

Prabhu Manyem, Shanghai University, PRC.

Article 2010-11

An Algorithm for Affine Approximation of Binary Decision Diagrams

Kevin Henshall
Department of Computer Science and Software Enginering
The University of Melbourne, Victoria 3010, Australia,
Peter Schachte
Department of Computer Science and Software Enginering
The University of Melbourne, Victoria 3010, Australia,
Harald Søndergaard
Department of Computer Science and Software Enginering
The University of Melbourne, Victoria 3010, Australia
and
Leigh Whiting
Department of Computer Science and Software Enginering
The University of Melbourne, Victoria 3010, Australia.

June 22, 2010

Abstract

This paper is concerned with the problem of Boolean approximation in the following sense: given a Boolean function class and an arbitrary Boolean function, what is the function's best proxy in the class? Specifically, what is its strongest logical consequence (or envelope) in the class of affine Boolean functions. We prove various properties of affine Boolean functions and their representation as ROBDDs. Using these properties, we develop an ROBDD algorithm to find the affine envelope of a Boolean function.

The article: PDF (682,927 bytes)
Source materials: ZIP (215,305 bytes)
Self citation in BIBTeX (336 bytes)
Original version (pre-June 2010): PDF (222,859 bytes)

DOI: 10.4086/cjtcs.2010.011

Licensed under a Creative Commons Attribution License

Special Issue, CATS 2009, Article 7

Article 9

Special Issue [back]

Published articles