Immediate Decompositions are those that are very good, happen relatively rarely, and if encountered, should be immediately executed. The Immediate Decompositions are: Strong Basic Gate Decompositions (Strong EXOR Decomposition, Strong AND Decomposition, Strong OR Decomposition), Strong Complex Gate Decompositions (section 3); Strong PUB Decompositions; and the Ashenhurst Decomposition. (The PUB decompositions [15] will be not discussed because of lack of space). All these decompositions can be efficiently found in CDBs using cofactors and set-theoretical operations [15]. Let us make a point that the more strongly is the function unspecified and the larger is set C, the more probable is that an Immediate Decomposition will exist for this function.
Existence of the Ashenhurst Decomposition can be checked either using Property 1, or Property 2.
Property 1. Ashenhurst Decomposition
F = 
with bound set 
, free set 
,
and single-output binary function G exists if
all row patterns are: ON Pattern, OFF Pattern, F Pattern and 
Pattern.
Property 2.
Ashenhurst Decomposition with bound set and free set exists if
all column patterns are F1 Pattern and F2 Pattern, F2 
F1.
In other words, column multiplicity index 
= 2.
Both these properties can be used to verify the existence of Ashenhurst Decomposition. Traditionally, for incompletely specified functions, the Ashenhurst and Curtis decompositions were reduced either to the clique partitioning of the Column Compatibility Graph or the graph coloring of the Column Incompatibility Graph [10, 9, 12, 13, 15, 16]. All these problems are in general NP-hard. However, in case of Ashenhurst decomposition, the problem can be solved by a polynomial algorithm. The following algorithm is based on Property 1.
Algorithm 1.
1. Remove from RVM all rows that correspond to ON, OFF and DC Patterns.
2. Find two rows, 
and 
that are incompatible,
and remove them. From remaining rows create the set 
.
3. Pair_Counter := 1.
4. Put row to LEFT[Pair_Counter] and row to RIGHT[Pair_Counter].
5. Take next row 
in set and remove it from set .
6. Compare with arrays LEFT and RIGHT.
a) If there exists a pair (LEFT[k], RIGHT[k]) such that
is incompatible with both LEFT[k] and RIGHT[k],
then exit "No Ashenhurst Decomposition".
b) Else if for all v from 1 to Pair_Counter is
compatible with LEFT[v] and is
compatible with RIGHT[v]
then
if RIGHT[Pair_Counter] 
then
Pair_Counter := Pair_Counter + 1;
put to LEFT[Pair_Counter];
else
LEFT[Pair_Counter] :=
Combine_Rows( , LEFT[Pair_Counter]);
c) Else Combine(LEFT,RIGHT, ).
7. If there are still rows in , go to 5.
8. Combine all sets LEFT[i] (i=1,...,Pair_Counter) to set LEFT, Combine all sets RIGHT[i] (i=1,...,Pair_Counter) to set RIGHT.
9. Return pair ( LEFT, RIGHT ) as the 2-coloring of the Compatibility Graph.
Procedure Combine_Rows( , 
) combines row with row ,
position by position in a row, using the combining
rules: 
:= combine ,
:= combine dont'care,
Procedure Combine(LEFT,RIGHT, ).
1. Find set of such indices vl=1,...,Pair_Counter
that is incompatible with LEFT[vl].
Combine all their RIGHT[vl] to RIGHT1
and all their LEFT[vl] to LEFT1.
RIGHT1 := Combine_Rows( , RIGHT1).
2. Find set of such indices vr=1,...,Pair_Counter
that is incompatible with RIGHT[vr].
Combine all their RIGHT[vr] to RIGHT2
and all their LEFT[vr] to LEFT2.
LEFT2 := Combine_Rows( , LEFT2).
3. RIGHT3 := Combine_Rows(RIGHT1, LEFT2).
LEFT3 := Combine_Rows(RIGHT2, LEFT1).
4. Remove all rows vl and vr from arrays LEFT
and RIGHT, append combined row RIGHT3 to the
end of array RIGHT, append combined
row LEFT3 to the end of array LEFT.
Algorithm 1A, based on Property 2, can be applied to mv-output functions and is very similar; Algorithm 1 is usually more efficient, but can be applied only to binary-output functions.