QBF-Based Boolean Function Bi-Decomposition

Details QBF-Based Boolean Function Bi-Decomposition QBF-Based Boolean Function Bi-Decomposition

2011-12-11

arxiv.org/abs/1112.2313v2

Computer Science

Logic in Computer Science

This paper is an extension of the DATE'2012 paper "QBF-Based Boolean Function Bi-Decomposition" by Huan Chen, Mikolas Janota,

Scientific paper

Boolean function bi-decomposition is ubiquitous in logic synthesis. It entails the decomposition of a Boolean function using two-input simple logic gates. Existing solutions for bi-decomposition are often based on BDDs and, more recently, on Boolean Satisfiability. In addition, the partition of the input set of variables is either assumed, or heuristic solutions are considered for finding good partitions. In contrast to earlier work, this paper proposes the use of Quantified Boolean Formulas (QBF) for computing bi- decompositions. These bi-decompositions are optimal in terms of the achieved disjointness and balancedness of the input set of variables. Experimental results, obtained on representative benchmarks, demonstrate clear improvements in the quality of computed decompositions, but also the practical feasibility of QBF-based bi-decomposition.

Affiliated with

Also associated with

No associations

Rating

QBF-Based Boolean Function Bi-Decomposition does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with QBF-Based Boolean Function Bi-Decomposition, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and QBF-Based Boolean Function Bi-Decomposition will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-306704