文档介绍：ADVANCED BDD OPTIMIZATION
Advanced BDD Optimization
by
RÜDIGER EBENDT
University of Bremen, Germany
GÖRSCHWIN FEY
University of Bremen, Germany
and
ROLF DRECHSLER
University of Bremen, Germany
A . Catalogue record for this book is available from the Library of Congress.
ISBN-10 0-387-25453-6 (HB) Springer, Dordrecht, Berlin, Heidelberg, New York
ISBN-10 0-387-25454-4 (e-book) Springer, Dordrecht, Berlin, Heidelberg, New York
ISBN-13 978-0-387-25453-1 (HB) Springer, Dordrecht, Berlin, Heidelberg, New York
ISBN-13 978-0-387-25454-8 (e-book) Springer, Dordrecht, Berlin, Heidelberg, New York
Published by Springer,
. Box 17, 3300 AA Dordrecht, herlands.
Printed on acid-free paper
All Rights Reserved
© 2005 Springer
No part of this work may be reproduced, stored in a retrieval system, or transmitted
in any form or by any means, electronic, mechanical, photocopying, microfilming, recording
or otherwise, without written permission from the Publisher, with the exception
of any material supplied specifically for the purpose of being entered
and executed on puter system, for exclusive use by the purchaser of the work.
Printed in herlands.
Contents
Preface ix
1
2. PRELIMINARIES 9
Notation 9
Boolean Functions 10
position of Boolean Functions 12
Reduced Ordered Binary Decision Diagrams 14
Syntactical Definition of BDDs 15
Semantical Definition of BDDs 18
Reduction Operations on SBDDs 20
Variable Orderingsof BDDs 24
BDD Levels and their Sizes 27
Implementation of BDD Packages 29
Basic Minimization Algorithm 32
Evaluation with BDDs 35
Paths in BDDs 37
MINIMIZATION45
Branch and Bound Algorithm 47
Classical Approach 47
Lower Bound Technique 52
Algorithm 60
Experimental Results 63
A∗-based Optimization 67
∗
State Space Search by A -Algorithm 67
Best-First Search A