Patent Publication Number: US-2002013775-A1

Title: Method of processing a request to a boolean rule and a computer readable medium encoded with a program for performing said method

Description:
FIELD OF THE INVENTION  
       [0001] The invention relates to the field of processing a request to a rule by the use of an input signal, compressed rule information, and an output signal.  
       BACKGROUND OF THE INVENTION  
       [0002] This invention relates to the European patent EP 0 456 675, where an input signal has components or elements representing aspects of a physical entity which are in a known state and other components or elements which are unknown. EP 0 456 675 provides a method and an apparatus which processes the signal in accordance with stored data representing rules which indicate which combinations of the components are possible. Rules are identified involving the known components or elements, and all of the combinations consistent with the known states are identified. If all of these combinations have the same value for a particular element, the element is determined to have that value in the output signal. The rules are stored as binary representations of the possible combinations, and the elements of the input and output signals may represent two allowable states, tautology (undefined state), and inconsistency (inallowable state).  
       [0003] However, the method disclosed in EP 0 456 675 which uses the positive index form for the representation of rules consumes much memory, especially when the rules comprise a large number of variables. Generally, the method requires storage of N/2*(2^ N) terms, where N is the number of variables in the formula. This means that a rule like  
       A B or C or D or E or F or G or H or I or J or K or L or M or N or 0 or P  
       [0004] takes up 64 k 16-bits words in memory; with this invention it is possible to compress the representation of the rule such that it takes up only 32 16-bits words in the memory and may be scanned about 2000 times faster in run time.  
       [0005] A special aim of the method disclosed in EP 0 456 675 and the present invention is to use the methods in configuration systems. However, the method is applicable in other fields e.g. in scheduling and planning.  
       [0006] A computer system intended to solve a configuration problem, is a special application of artificial intelligence where the problem can be stated in terms of a set of selectable elements, and a number of relations between these selectable elements. The configuration problem is solved when the set of all selectable elements is completely divided into two disjunct sub-sets representing elements that are included in the configuration and elements that are excluded from the configuration, respectively, without violating any of the relations between the selectable elements.  
       [0007] A selectable element is anything that can be included or excluded. It can be a physical object (e.g. a car or a specific kind of engine), an attribute (e.g. the color red or the texture pattern of a carpet) or something abstract (e.g. a specific number of trips between home and work or a particular type of contract).  
       [0008] A relation is a rule involving one or more selectable elements. The purpose of a rule is to constrain the selection of elements to obey some requirements. A rule can be based on a physical limitation (e.g. if a car needs a large engine to support a large number of selected electrical accessories), or a discretionary decision (e.g. if management decides that all cars having a particular large engine are produced only in red to give them a more sporty look). Often the term ‘Constraint’ is used to refer to a rule limiting the elements that can be combined.  
       CROSS REFERENCES  
       [0009] Reference is made to the following patent applications, filed the same day as this application and assigned to the same assignee, Beologic A/S:  
       [0010] (1) A Method of Configuring a Set of Objects in a Computer  
       [0011] (2) A Method and Apparatus for Inference of Partial Knowledge in Interactive Configuration  
       [0012] (3) Configuration via Network  
       [0013] (4) A method of enabling Invalid Choices in Interactive Configuration Systems  
       [0014] which are hereby incorporated as references to be understood in connection with the present invention.  
       SUMMARY OF THE INVENTION  
       [0015] An object of the invention is to provide a method which allows fast processing of a request to rule, such that it is verified whether the request violates the rule, i.e. is in contradiction with the rule, and such that unknown information in the request may be, but not necessarily is determined.  
       [0016] There is provided a method of processing a request to a rule by the use of an input signal, compressed rule information, and an output signal, comprising the steps of: representing said input signal as a plurality of two-bit pairs, each pair corresponding to a variable in said input signal; representing the rule information with at least a first and a second type of terms; each of said terms of the first type being binary words and each representing one allowable combination of the variables; each of said terms of the second type being a plurality of two-bit pairs and representing at least two allowable combinations of the variables; testing whether there is a first type of match between at least one of said first terms and said input signal; testing whether there is a second type of match between at least one of said second terms and said input signal; generating an output signal as a plurality of two-bit pairs, each pair corresponding to a variable in said input signal; updating said output signal according to the following strategy: if there is a match of said first type, then the output signal is updated with values which are responsive to at least one of said first type of terms; if there is a match of said second type, then the output signal is updated with values which are responsive to at least one of said second type of terms.  
       [0017] There is thereby provided a method which combines a compressed and uncompressed term representation for a rule, which is very fast regarding computational time and which is very efficient regarding memory consumption.  
       [0018] This is possible in particular when the method comprises the step of: generating said input signal as a subset of variables from a global input signal, wherein said subset of variables is determined as those variables involved in said rule.  
       [0019] The computational effort required for the processing of a request may hereby be reduced significantly if an actual rule only involves a limited subset of a large set of variables.  
       [0020] Since the processing of the request results in an output signal, it is moreover expedient if the method further comprises the step of: generating a global output signal having variables, wherein some of the variables are updated with variable values from said output signal.  
       [0021] Thereby, the information in the limited subset is transferred to the large set of variables.  
       [0022] Alternatively, there is provided a method of processing a request to a rule by the use of an input signal, compressed rule information, and an output signal, comprising the steps of: representing the input signal as a plurality of two-bit pairs, each pair corresponding to a variable in the input signal, representing the rule information with at least one type of terms, each of the terms of said type being a plurality of two-bit pairs and representing at least one allowable combination of the variables, testing whether there is a match between at least one of said terms and said input signal, updating an output signal which is a plurality of two-bit pairs such that if there is a match, then the output signal is updated with values which are responsive to at least one of said terms.  
       [0023] Further, there is provided a method of processing a request to a rule by the use of an input signal, compressed rule information, and an output signal, comprising the steps of: representing said input signal as a plurality of bit structures, each structure corresponding to a variable in said input signal; representing the rule information with at least a first and a second type of terms; each of said terms of the first type being binary words and each representing one allowable combination of the variables; each of said terms of the second type being a plurality of bit structures and representing at least two allowable combinations of the variables; testing whether there is a first type of match between at least one of said first terms and said input signal; testing whether there is a second type of match between at least one of said second terms and said input signal; generating an output signal as a plurality of bit structures, each structure corresponding to a variable in said input signal; updating said output signal correspondingly, if there is a match of one of said types.  
       [0024] Consequently, it is possible to represent terms for a rule, which is very fast regarding computational time and which is very efficient regarding memory consumption. Thereby it is possible to have only one type of terms and still feasible features such as computational time efficient memory consumption.  
       [0025] Further, the invention relates to a computer readable medium encoded with a program for performing the method as described above. 
     
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
     [0026] The invention will be explained more fully below in connection with a preferred embodiment and with reference to the drawing, in which:  
     [0027]FIG. 1 shows a flow chart for a method of generating a compressed rule representation;  
     [0028]FIG. 2 shows a parse tree for the formula: (X or Y) Z;  
     [0029]FIG. 3 shows four state vectors and indicates scanning of compressed and uncompressed terms according to the invention;  
     [0030]FIG. 4 is the overall structure of a preferred embodiment of the present invention;  
     [0031]FIG. 5 shows a flow chart for a method of generating a local input state vector from a global input state vector;  
     [0032]FIG. 6 shows a flow chart for a method of scanning uncompressed terms;  
     [0033]FIG. 7 shows a flow chart for a method of scanning compressed terms;  
     [0034]FIG. 8 shows a flow chart for a method of extracting information. 
    
    
     DETAILED DESCRIPTION OF A PREFERRED EMBODIMENT  
     [0035] In European Patent EP 0 456 675, which is hereby incorporated as a reference, a boolean formula is represented by the positive index form of that formula.  
     EXAMPLE 1  
     [0036] For the formula  
     A or !B !C  
     [0037] ‘if A or not B, then not C’, with the boolean variables A, B, and C, the positive index form is given in table 1.  
                                   TABLE 1                                   Term No.   A   B   C                          1   0   0   0           2   0   1   0           3   0   1   1           4   1   0   0           5   1   1   1                      
 
     [0038] The five terms in table 1 represent exactly all the combinations of the variables where the formula is valid (not violated).  
     [0039] In a computer the contents of table 1 could conveniently be represented by means of S bytes or one bit per variable per term in the memory.  
     [0040] According to the present invention the boolean rule representation is changed from the use of the two states true and false to the three states true, false, and don&#39;t care. The don&#39;t care state represents tautology which implies that a don&#39;t care state may take the value true as well as false without violating the represented rule. The don&#39;t care state is indicated by a star (*) in the representation of the positive index form of a formula.  
     [0041] The formula  
     A or !B !C  
     [0042] may thereby be represented as given in table 2.  
                                   TABLE 2                                   Term No.   A   B   C                          1, 4   *   0   0           2   0   1   0           3, 5   *   1   1                      
 
     [0043] Compared with table 1, table 2 comprises two rows less than table 1. It is clear from table 2 that the last row may be expanded to the terms 3 and 5 in table 1. A compressed rule representation is hereby introduced.  
     [0044] On a computer, the compressed positive index form utilizes faster execution speed and consumes less memory. One term that includes a don&#39;t care “*” can be represented with a two bit representation for each variable. The three symbols {0,1,*} used for the compressed representation are shown in table 3 along with the binary assignment of the bits S 1  and S 2  in the two bit representation.  
                               TABLE 3                                   True   False   Don&#39;t care           (1)   (0)   (*)                                                            S1   0   1   1           S2   1   0   1                      
 
     [0045] The exact choice of bit combinations is very important to the rule scanning algorithm because essential operations can be made with simple and/or operations. The bit combinations may be chosen such that those operations which are assumed to be executed most frequently are the fastest operations to execute. The compressed version may conveniently be represented by 5 bytes in the memory i.e. two bytes per compressed term and one byte per uncompressed term. However, for rules with more variables significant memory savings can be achieved.  
     EXAMPLE 2  
     [0046] For the rule  
     A or B or C or D or E or F or G or H or I or J K                TABLE 4                          The positive index form is given in table 4:                                                             Term No.   A   B   C   D   E   F   G   H   I   J   K               1   0   0   0   0   0   0   0   0   0   0   0       2   0   0   0   0   0   0   0   0   0   0   1       2   0   0   0   0   0   0   0   0   0   1   1       4   0   0   0   0   0   0   0   0   1   0   1       . . .    . . .        1025   1   1   1   1   1   1   1   1   1   1   1                    
     [0047] The uncompressed terms in table 4 requires two bytes times 1025 terms, equal to 2050 bytes. The compressed term representation is given in table 5.  
                                                           TABLE 5                       Term No.   A   B   C   D   E   F   G   H   I   J   K                  2-1025   *   *   *   *   *   *   *   *   *   *   1       1 ,2   0   0   0   0   0   0   0   0   0   0   *                  
 
     [0048] This compressed representation requires two bytes times two bytes per term times two terms, equal to eight bytes.  
     [0049] For this rule, a significant saving is obtained in memory consumption, even though the compressed term representation uses twice as much memory per term, i.e. two bits per variable.  
     [0050] The generation of compressed terms is well known from the field of digital design. Karnaugh cards are one method and a method such as the Quine-McCluskey method (1965) can be found in Morris Mano&#39;s book Digital Design. An overlapping set of terms is generated by the Quine-McCluskey method.  
     [0051] However, we use a method by Antoine Rauzy “Boolean Unification, an efficient algorithm” 1989. This method generates a non overlapping set of terms.  
     [0052] The principle of the algorithm is to construct a decision tree recursively. Let f be a formula. The application of the algorithm for f can be viewed as a succession of couples &lt;ActiveList; ResultList&gt; where ActiveList is a sequence of open tableaux labelings, the unexplored nodes of the tree. ResultList is a set of open tableaux labelings reached in the previous steps and such that the reductions of the labeling are equal to true in the formula f.  
     [0053]FIG. 1 shows a flow chart for a method of generating a compressed rule representation. In step 1, the method begins with a symbolic boolean formula which is subject for a compressed representation. In step 2 an initialization process comprises assigning of the variables ActiveList and ResultList to the empty set and T to the empty set. When the initialization is done, a variable Q in the formula f, which is not in the term T at present, is selected in step 3. If several variables are possible, then the topmost one in the associated parse tree (see FIG. 2) is selected, i.e. the variable governed by the fewest operators is selected. In case of ties, a variable is chosen at random. In step 4 the two terms T 1  and T 2  are generated, where T 1  is T with Q added and T 2  is T with the negated Q added. Each term respectively represents one side of the parse tree. Furthermore a counter i is initialized. Then a loop is entered, and the first step 5 of the loop is to increment the counter, i.e. i is set equal to i+1. The next step 6 in the loop is to compute the truth value of the function f with respect to the known variable values in T 1  or T 2  that is the value of f(Ti). The truth value is calculated by means of a calculator which uses the rewrite rules given in table 6. The symbol A may represent both a variable and a sub-formula.  
                           TABLE 6                                   Rule No.   Rules                          R1   false and A :  false           R2   false or A :  A           R3   false   A :  true           R4   A   false :  not A           R5   false   A :  not A           R6   not false :  true           R7   false xor A :  A           R8   true and A :  A           R9   true or A :  true           R10   true   A :  A           R11   A   true :  true           R12   true   A :  A           R13   not true :  false           R14   true xor A :  not A                      
 
     [0054] The rewrite rules are derived directly from the Boolean algebra. If all variables are known then it is easy to determine the truth value of the formula f, however with only partial assignment the truth value may be undetermined in some cases.  
     [0055] It is only necessary to compress a rule once, since the rule representation may be stored.  
     [0056]FIG. 2 shows a parse tree for the formula: (X or Y) Z. The top node of the tree corresponds to the ‘ ’ or implication in the formula. The other node corresponds to the or-operator. X, Y, and Z are the variables of the parse tree.  
     EXAMPLE 3  
     [0057] For the formula  
     (X or Y) Z  
     [0058] where Z is equal to True (Z:=true), the formula is  
     (X or Y) True  
     [0059] according to R 11  the formula is “True”, i.e. the truth value is True irrespective of the assignment of X and Y. For another term T=!XY, the formula is  
     (False or True) Z  
     [0060] according to R 9  “True Z” and according to R 10  “Z”, and therefore the truth value cannot be determined in this case. In the event that the truth value of the formula cannot be determined, the result of the computation in step 6 is ‘unkonwn’, and then Ti is added to the Active-List in step 7 for further processing in loop comprising the steps 3 to 11. In the event that the truth value of the formula is evaluated to be ‘True’ in step 6, then the term T is added to the ResultList as a valid compressed term in step 8. In the event that the truth value of the formula is evaluated to be ‘False’ in step 6, or Ti is added to either the ResultList in step 8 or the Active-List in step 7, then it is tested in step 9 whether the counter i is equal to 2. If both T 1  and T 2  have been computed, it is tested in step 10 whether the ActiveList is empty, otherwise, if T 1  and T 2  have not been computed, the loop is resumed at step 5, where the counter i is incremented. In step 10 it is tested whether the ActiveList is empty. If it is empty, then the processing is terminated, otherwise a term T is subjected to further processing by taking T out of the ActiveList and resuming the loop in step 3.  
     [0061] If the ActiveList is empty at step 10, the result list contains a set of terms representing the positive index of the formula in compressed form. The terms are translated into the index form by means of table 7.  
                           TABLE 7                                   Term   Compressed Positive           Variable   Index                          A   1           !A   0           ‘Not occurring   *           in term but in           formula’                      
 
     [0062] Generally, this compressed formula representation takes up memory in the order of N times O bits, where N is the number of variables and O is the number of operators.  
     Examples of Compression:  
     EXAMPLE 4  
     [0063] In this example, the formula  
     (X or Y) Z  
     [0064] is subjected to a compressed term representation. The succesive updates of the ResultList and ActiveList are shown in table 8 below.  
                           TABLE 8                                   Active List (AL)   Result List (RL)                          []   []           [{Z}, {!Z}]   []           [{!Z}]   [{Z}]           [{Y, !Z}, {!Y, !Z}]]   [{Z}]           [{!Y, !Z}]]   [{Z}]           [{X, !Y, !Z}, {!X, !Y, !Z}]   [{Z}]           [{!X, !Y, !Z}]   [{Z}]           []   [{!X, !Y, !Z}, {Z}]                      
 
     [0065] Therefore, the compressed positive index form is given as shown in table 9.  
                                   TABLE 9                                   Term No.   X   Y   Z                          1   0   0   0           2   *   *   1                      
 
     EXAMPLE 5  
     [0066] In this example, the formula  
     X (Y or Z)  
     [0067] is subjected to a compressed term representation. The succesive updates of the ResultList and ActiveList are shown in table 10 below.  
                           TABLE 10                                   Active List (AL)   Result List (RL)                          []   []           [{X}, {!X}]   []           [{X,Y}, {X, !Y}]   [{!X}]           [{X, !Y}]   [{!X}, {X,Y}]           [{X, !Y,Z}, {X, !Y, !Z}]   [{!X}, {X,Y}]           []   [{!X}, {X,Y}, {X, !Y,Z}]                      
 
     [0068] Therefore, the compressed positive index form is given in table 11.  
                                   TABLE 11                                   Term No.   X   Y   Z                          1   0   *   *           2   1   1   *           3   1   0   1                      
 
     [0069] To optimize the use of memory, the terms that do not have any don&#39;t cares * will be kept in a list separate from those that don&#39;t cares *.  
     [0070] A Boolean formula is henceforth represented as a structure with three elements  
     Formula=(VL, PIL, CPIL)  
     [0071] where VL is Variable List, PIL is an uncompressed Positive Index List, and CPIL is a Compressed Positive Index List, containing a list of pairs {S 1 , S 2 }.  
     EXAMPLE 5 (CONTINUED)  
     [0072] Remembering the Boolean rule  
     X (Y or Z),  
     [0073] the contents of the ResultList in table 10 and the translations given in table 3 and 7, give the data representation of the formula  
     Formula=([X,Y,Z], [101], [{001,111},{111,011}])  
     EXAMPLE 2 (CONTINUED)  
     [0074] Remembering the Boolean rule  
     A or B or C or D or E or F or G or H or I or J K,  
     [0075] the term representation in table 5 gives the data representation of the formula:  
     Formula=([A,B,C,D,E,F,G,H,I,J,K], [000000 00000], [{11111111110,11111111111}])  
     [0076] Thus it is clear that this representation is very efficient.  
     [0077]FIG. 3 shows four state vectors and indicates scanning of compressed and uncompressed terms according to the invention. The overall structure of the scanning algorithm is divided into four stages. At stage one a request to a rule is prepared. The request is in the form of a state vector, and the rule is in the form of a formula represented by the compressed and uncompressed terms. That is, a local input state vector (ISV)  303  with elements  304  is generated by extracting information from the global state vector  301  with elements  302 . The information is extracted such that only the variables involved in the formula are extracted. This minimizes the computational effort required in the processing of the request to the rule. The processing comprises two stages: scanning of compressed and uncompressed terms.  
     [0078] At stage two  305  the local input state vector is scanned through all uncompressed terms of the formula to test for ‘match’ or no ‘match’, and the relevant elements  307  of the local output state vector (OSV)  306  are updated with the result of the uncompressed scanning.  
     [0079] At stage three  310  the local input state vector (ISL)  303  is scanned through all the compressed terms of the formula to test for ‘match’ or ‘no match’. The information retrieved by the scanning is contained in the local output state vector (OSV). At stage four the contents of the local output state vector are transferred to the global output state vector  308  with elements  309 .  
     [0080] A request in the form of an input state vector comprises information about known aspects of an element, for example the state of sensors or configuration selections, but generally other elements of the state vector will be unknown. The information may be contained in elements of a state vector having variable values. The request processing at stage two and four scans a Boolean formula with the knowledge of the current assignments of variables found in the state vector. One object of the invention is to determine some or all of the unknown elements where the rule enables this. The result of the request is updated in the output state vector.  
     [0081] If a contradiction between the request and the rule is detected, i.e. the formula is violated, then the algorithm ends, and if the formula is valid, it is determined whether any further variables may be deduced, i.e. assigned a value in the state vector. The state vector can physically be any data repository such as a data base or a set of objects with associated values about a set of Boolean items occurring in the formula.  
     [0082] The input state vector and the output state vector comprise the variable values which occur in the formula. Each variable in the state vector is stored in the form of one of four possible two-bit combinations.  
                                   TABLE 12                                   True   False   Tautology   Contradicion           (1)   (0)   (*)   (!)                                                        S1   0   1   1   0       S2   1   0   1   0                  
 
     [0083] Table 12 shows the possible variable values of the two bits S1 and S2 in the state vector.  
     [0084] It should be noted that this is the same convention as used for representing the compressed terms for the symbolic values ‘True’, ‘False’, and ‘Tautology’ (don&#39;t care).  
     [0085] The scanning process can be seen as looking at the terms of the formula one by one. If there is a match between the variables bound in the input state vector and the terms (i.e. the rule representation), then the unbound variables may have the value represented in the term. Bounded variables may take the symbolic values ‘True’ or ‘False’, whereas unbounded variables may take the symbolic value ‘Tautology’.  
     [0086] The following table determines whether a match exists or not between a rule term and an input state vector variable. A match between a term and the input state vector is detected if all the variables of that term match with the input state vector.  
                       TABLE 13                          0   0   Match       0   1   No Match       0   *   Match       1   1   Match       1   *   Match       *   *   Match                       # and ‘*’ (don&#39;t care/tautology) result in a ‘match’ or ‘no match’.           
 
     [0087] When looking at the actual chosen bit representation, both bits have to differ in order to detect a ‘no match’.  
     [0088] When a match has been detected, the knowledge about the matching term is stored in an output state vector using the following update table.  
                       TABLE 14                           Output   New Output           State   State       Term   Vector   Vector       Variable   Variable   Variable                  0   !   0       1   !   1       *   !   *       1   0   *       0   1   *       *   0   *       *   1   *       0   0   0       1   1   1       *   *   *                       # previous output state vector.           
 
     [0089] When looking at the chosen bit representation given in table 12 and the output update in table 14, it is now possible to update the output state vector by a simple Boolean OR operation.  
     EXAMPLE 5 (CONTINUED I)  
     [0090] Remember the rule  
     X (Y or Z),  
     [0091] now with a request where external assignments have been made in the state vector. The assignment is that Z is set to false, X is set to true, and there is no knowledge about Y, i.e. tautology. The input state vector is  
     [ X Y Z]=[ 1*0] 
     [0092] and the term representation is as given in table 11.  
                                       TABLE 15                              X   Y   Z                           Input State       Vector =   [1   *   0]                                   Output State   Step                           Vector =   No                                                         term 1 →   0   *   *   → No match   [!   !   !]   1       term 2 →   1   1   *   → Match   [1   1   *]   2       term 3 →   1   0   1   → No Match   [1   1   *]   3                  
 
     [0093] Table 15 shows the input state vector, the representation of terms 1, 2, and 3 and the three succesive updates of the output state vector. The output state vector is by default initialized to ‘contradiction’ (!) for all elements in the output state vector. Thus, because no match is found between the input state vector and term 1, the output state vector is not updated in step 1. In step 2 there a match is detected, and therefore the output state vector is updated according to table 14. In step 3 there no match is found either, and the output state vector remains unchanged. Match/no match is detected by means of table 13.  
     [0094] Now when looking at the output state vector and eliminating those elements that were bound in the input state vector, it can be seen that Y must be true according to the rule terms. This implies that Y may take the value True and may now be transferred to the output state vector with that value.  
     [0095] The bitwise determination of whether there is a match or not and the updating of the output variables can be done by the four operations “and, or, not, xor”, if the representations given in table 3 and 12 is used. Generally, a computer executes these basic operations very fast. If the signal components S 1  and S 2  are represented by means of e.g. two words, then a 32-bit computer can execute a term match process in two basic operations for formulas with less than 32 variables. Rules with less than 32 variables are the most common rules.  
     [0096]FIG. 4 is the overall structure of a preferred embodiment of the present invention. The structure is divided into four stages i.e.  414 ,  415 ,  416 , and  417 . The detailed method used in a preferred embodiment is presented in each of these four stages. Start  413  and end  418  indicates where the method is initiated and where no further processing takes place. Stage one  414  corresponds to the global to local input state vector conversion in FIG. 3, and stage four corresponds to the local to global output state vector conversion.  
     [0097] Description of Variables in Scanning Algorithm:  
     [0098] StateVector: Is a vector where all the variables are represented by their current value. The value of StateVector[A] is the current truth value of A (True, False, Unbound).  
     [0099] TV is a bit mask indicating the True variables in input state vector with a binary ‘1’.  
     [0100] BV is a bit mask indicating the bounded variables in input state vector with a binary ‘1’.  
     [0101] ISV is the local input state vector.  
     [0102] OSV is the local output state vector.  
     [0103] CH is a bit mask indicating the changed variables in input state vector with a binary ‘1’. . . .  
     [0104] All operators (and, or, xor, not) are.  
     [0105] |X| means the length of X, e.g. |X|=|{a,b,s,d}|4.  
     Formula=(VL, PIL, CPIL), where  
     [0106] VL is a variable list.  
     [0107] PIL is a positive index list.  
     [0108] CPIL=[{S 1 , S 2 }] is a compressed positive index list of pairs {S 1 , S 2 }.  
     [0109]FIG. 5 shows a flow chart of a method of generating a local input state vector from a global input state vector. Start  519  is similar to start  413  of FIG. 4. First, a counter i is initialized to zero in step  520  in order to count over the variables in the formula. Then a loop is entered, and the first step  521  in the loop is to increment the counter i to i+1. The counter is used as an index in the formula variable list VL to get the variable which is again used as an index in the StateVector to extract the actual value of the variable either True, False or Unbound. In step  522  the variable value of the element number i in Formula.VL is recognized as either true (T), false (F), or unbound (UB). If the result of step  522  is true, then step  523  is entered, if the result is unbound, then step  524  in entered, and if the result is false, then step  525  is entered. In step  523  the bits S 1  and S 2  of variable number i are updated with S 1 :=0 and S 2 :=1. In step  524  the bits S 1  and S 2  of variable number i are updated with S 1 :=1 and S 2 :=1. In step  525  the bits S 1  and S 2  of variable number i are updated with S 1 :=1 and S 2 :=0. The loop is repeated until the truth value of all the variables in the formula has be transferred to the local input state vector (ISV). This is tested in step  526 . If the counter i has reached the length of the formula variable list Formula.VL, then the loop is terminated, otherwise the loop is resumed with a counter increment in step  521 . If the loop is terminated, the method continues with the scanning of uncompressed terms via the step A,  527 .  
     [0110]FIG. 6 shows a flow chart of a method of scanning uncompressed terms. The method of FIG. 5 continues via step A,  527 . In step  627  initialization of variables regarding the scanning of uncompressed terms is performed. The local output state vector OSV is initialized to ‘contradiction’ by setting the two bits S 1  and S 2  to ‘ 0 ’. That is OSV[i] S 1 :=0, OSV[i].S 2 :=0, corresponding to that all elements are set to 0. The bounded variables in the local input state vector ISV are indicated with a bit mask BV by a binary ‘1’, that is BV:=not (ISV.S 1  and ISV.S 2 ). The true variables of the local input state vector are also indicated by a bit mask TV:=BV and ISV.S 2 . And finally the variable AnyMatch is set to false, Anymatch:=False. In step  628  the counter i is set to zero, i:=0. This counter is used to count over the uncompressed terms in the positive index list, PIL, of the formula. Step  629  increments the counter i and is the first step of a loop. The loop is terminated in step 630 if all the PIL terms have been scanned, here tested whether the counter i has reached the length of the formulas PIL list, that is, is i=|Formula.PIL|. Detection of whether there is a match or not is carried out in step 631, wherein the truth value of the statement  
     TV=Formula.PIL[i] and BV  
     [0111] is tested. If this statement is false, then the loop is resumed with a counter increment in step 629, otherwise the local output state vector is updated along with the variable AnyMatch, before the loop is resumed in step  629 . The update is as follows:  
     OSV.S 1 :=OSV.S 1  or not (Formula.PIL[i])  
     OSV.S 2 :=OSV.S 2  or Formula.PIL[i] 
     AnyMatch:=True  
     [0112] If no match exists, then the OSV is not updated and a contradiction is detected. When the loop is finished, as detected in step  630 , the method continues with scanning of the compressed terms via the step B,  633 .  
     [0113]FIG. 7 shows a flow chart of a method of scanning compressed terms. The method of FIG. 6 continues via the step B,  633 . In step  733  the counter i is set to zero, i:=0. The counter is used to count over the compressed terms in the compressed positive index list, CPIL, of the formula. Step  734  increments the counter i and is the first step of a loop. The loop is terminated in step 735 if all the CPIL terms have been scanned, here tested whether the counter i has reached the length of the formulas CPIL list, that is, is i=|Formula.CPIL|. Detection of whether there is a match or not is carried out in step  736 , wherein the truth value of the statement  
     0=((Formula.CPIL[i].S 1  xor ISV.S 1 ) and  
     (Formula.CPIL[i].S 2  xor ISV.S 2 ))  
     [0114] is tested. If this statement is false, then the loop is resumed with a counter increment in step  734 , otherwise the local output state vector is updated along with the variable AnyMatch, before the loop is resumed in step  629 . The update is as follows:  
     OSV.S 1 :=OSV.S 1  or Formula.CPEL[i].S 1   
     OSV.S 2 :=OSV.S 2  or Formula.CPEL[i].S 2   
     AnyMatch:=True  
     [0115] If no match exists, then the OSV is not updated and a contradiction is detected. When the loop is finished, as detected in step  735 , the method continues with an information extraction via step C,  738 .  
     [0116]FIG. 8 shows a flow chart of a method of extracting information. The method of FIG. 7 continues via the step C,  738 . If no match is detected in step  838 , for either the compressed or uncompressed terms, then the request in the form of the input state vector is in contradiction with the rule representation and thereby the rule. This result is provided in step  839  if the variable AnyMatch is false. Alternatively the detection is performed by calculating the truth value of the statement: 0=(OSV.S 1  or OSV.S 2 ).  
     [0117] The variable that has been changed due to the scanning process es extracted by comparing the local input state vector (ISV) to the output state vector (OSV) and removing all bound variables indicated by BV in the change vector CV. That is, a true variable could match a unbound variable. The changed variables are indicated in step 840 in the vector CH by means of the statement:  
     CH:=(ISV.S 1  xor OSV.S 1 ) or (ISV.S 2  xor OSV.S 2 ) and not (BV)  
     [0118] If the change vector only contains zeros, then the scanning has reveiled no new information, and the algorithm may then report this. That is, the request is valid according to the rule. In step  841  it is tested whether CH is equal to 0, and if CH is equal to 0, then in step  842  it is concluded that nothing is deduced and the method terminates. The method ends, and it has deduced variables which are reported. In step  841  the counter i is incremented in the beginning of the loop. This loop is repeated until the truth value af all the deduced variables in the local output state vector (OSV) have been transferred to the StateVector SV, here tested in step 844 whether the counter i has reached the length of the formula variable list VL. That is, is i&lt;|Formula.VL|?. If the result is no, then the method terminates in step  849 , otherwise the method continues in step  845 . In step  845  it is tested whether the value of element i in the vector CH is true. If the value of the element is true, then it is tested, in step  846 , whether bit S 1  in the element i of the local output state vector is true, that is is OSV[i].S 1 =0 ?. If it is true, then the StateVector[Formula.VL[i]] is set to true in step  847 , otherwise StateVector[Formula.VL[i]] is set to false. When step  847  or step  848  is executed, then the loop resumes with a counter increment in step  843 . Likewise, the loop resumes if the result of step  845  is false.  
     EXAMPLE 5 (CONTINUED II)  
     [0119] Remember the rule  
     X (Y or Z)  
     [0120] where the formula representation is  
     {[X,Y,Z], [101], [{111,011},{001,111}]}.  
     [0121] Furthermore, it is known that X is assigned to true and Z is assigned to false.  
     [0122] Start at stage one: Generate local input state vector  
     [0123] (X) StateVector[1]=True  
     [0124] (Y) StateVector[2]=Unbound  
     [0125] (Z) StateVector[3]=False  
     [0126] isv={011, 110}, osv={000,000}, TV=[100], BV=[101] 
     [0127] Stage two: Scan uncompressed terms  
     [0128] Match ? (Formula.PIL[i] and BV) xor TV  
     [0129] PIL[1]: (101 and 101) xor 100=101 xor 101=001 (No match)  
     [0130] isv={011, 110}, osv {000,000}, TV=[100], BV=[101] 
     [0131] Stage three: Scan compressed terms  
     [0132] Match ? ((Formula.CPIL[1].s 1  xor isv.s 1 ) and (Formula.CPIL[1].s 2  xor isv.s 2 ))  
     [0133] [{111,011}, {001,111} 
     [0134] CPIL[1]: (111 xor 011) and (011 xor 110) 100 and 101=100 (No Match) Continue  
     [0135] CPIL[2]: (001 xor 011) and (111 xor 110)=010 and 001=000 (Match)  
     [0136] osv.s 1 :=osv.s 1  or Formula.CPIL[2].s 1 =000 or 001=001  
     [0137] osv.s 2 :=osv.s 2  or Formula.CPIL[2].s 2 =000 or 111=111  
     [0138] isv={011, 110}, osv={001,111}, TV=[100], BV=[101] 
     [0139] Stage four: Extract information from scanning  
     [0140] CH=((isv.s 1  xor osv.s 1 ) or (isv.s 2  xor osv.s 2 )) and !BV  
     [0141] =(011 xor 001) or (110 xor 111) and !101  
     [0142] =(010 or 001) and 010=011 and 010=010  
     [0143] Local StateVector[2]={0,1}=True  
     [0144] Therefore Y equals True, as expected.  
     EXAMPLE 6  
     [0145] This example is taken from the field of configuration.  
     [0146] The relations between the selectable elements for a car, the rule, or constraint may be:  
     [0147] Model[Turbo] or Model[Cabriolet] MetalicPaints and Trim[Leather] and CruiseControl  
     [0148] Instead of using the above terms we abbreviate these to more readable variable names:  
     [0149] Model[Turbo]=A  
     [0150] Model[Cabriolet]=B  
     [0151] MetalicPaints=C  
     [0152] Trim[Leather]=D  
     [0153] CruiseControl=E  
     [0154] The above constraint abbreviates to the following formula:  
     A or B C and D and E  
     [0155] We can now commence the Fast Boolean Scanning algorithm. Leftmost is the point at which the ActiveList and the ResultList are shown. p4 — 5 indicates the point between step  4  and step  5 , likewise p9 — 10 indicates the point between step  9  and step  10 . For each iteration it is shown what the terms T, T 1  and T 2  are assigned.  
                              Referring to FIG. 1 ‘generating a compressed rule repre-       sentation’:                         Point:   ActiveList:   ResultList:               p2_3   { }   { }                 T=0, T1=A, T2=!A                         p4_5   { }   { }       p4_5   {A}   { }       p9_10   {A, !A}   { }                 T=A, T1=AB, T2=A!B                         p4_5   {!A}   { }       p4_5   {!A, AB}   { }       p9_10   {!A, AB, A!B}   { }                 T=!A, T1=!AB, T2=!A!B                         p4_5   {AB, A!B}   { }       p4_5   {AB, A!B, !AB}   { }       p9_10   {AB, A!B, !AB}   {!A!B}                 T=AB, T1=ABC, T2 = AB!C                         p4_5   {A!B, !AB}   {!A!B}       p4_5   {A!B, !AB, ABC}   {!A!B}       p9_10   {A!B, !AB, ABC}   {!A!B}                 T=A!B, T1=A!BC, T2=A!B!C                         p4_5   {!AB, ABC}   {!A!B}       p4_5   {!AB, ABC, A!BC}   {!A!B}       p9_10   {!AB, ABC, A!BC}   {!A!B}                 T=!AB, T1=!ABC, T2=!AB!C                         p4_5   {ABC, A!BC}   {!A!B}       p4_5   {ABC, A!BC, !ABC}   {!A!B}       p9_10   {ABC, A!BC, !ABC}   {!A!B}                 T=ABC, T1=ABCD, T2=ABC!D                         p4_5   {A!BC, !ABC}   {!A!B}       p4_5   {A!BC, !ABC, ABCD}   {!A!B}       p9_10   {A!BC, !ABC, ABCD}   {!A!B}                 T=A!BC, T1=A!BCD, T2=A!BC!D                         p4_5   {!ABC, ABCD}   {!A!B}       p4_5   {!ABC, ABCD, A!BCD}   {!A!B}       p9_10   {!ABC, ABCD, A!BCD}   {!A!B}                 T1=!ABC, T1=!ABCD, T2 = !ABC!D                         p4_5   {ABCD, A!BCD}   {!A!B}       p4_5   {ABCD, A!BCD, !ABCD}   {!A!B}       p9_10   {ABCD, A!BCD, !ABCD}   {!A!B}                 T=ABCD, T1=ABCDE, T2=ABCD!E                         p4_5   {A!BCD, !ABCD}   {!A!B}       p4_5   {A!BCD, !ABCD}   {!A!B, ABCDE}       p9_10   {A!BCD, !ABCD}   {!A!B, ABCDE}                 T=A!BCD, T1 = A!BCDE, T2=ABCD!E                         p4_5   {!ABCD}   {!A!B, ABCDE}       p4_5   {!ABCD}   {!A!B, ABCDE, A!BCDE}       p9_10   {!ABCD}   {!A!B, ABCDE, A!BCDE}                 T=ABCD, T1=ABCDE, T2=ABCD!E                         p4_5   { }   {!A!B, ABCDE, A!BCDE}       p4_5   { }   {!A!B, ABCDE, A!BCDE,               !ABCDE}       End   { }   {!A!B, ABCDE, A!BCDE,               !ABCDE}                  
 
     [0156] The result can now be translated into the two-bit representation given in table 16:  
                                           TABLE 6                                   Term No.   A   B   C   D   E                          1   0   0   *   *   *           2   1   1   1   1   1           3   1   0   1   1   1           4   0   1   1   1   1                      
 
     [0157] Resulting in the following representation  
     Formula=([A,B,C,D,E], [11111,10111,01111], [{11111, 00111}])  
     [0158] Referring to FIG. 5 ‘generating a local input state vector’:  
     [0159] Now, in the formula A or B C and D and E a user may have chosen B=False and E=True corresponding to having made the choices of discarding the Cabriolet model, but selecting Cruise Control.  
     [0160] Initially, we have the following data structures from above:  
     [0161] Formula.VariableList=[A,B,C,D,E] 
     [0162] Formula.PositiveIndexList=[11111,10111,01111] 
     [0163] Formula.CompressedPositiveIndexList=[{11111,00111}] 
     [0164] At the point A (after the first loop) the InputStateVector has been assigned.  
     [0165] isv.s 1 =11110  
     [0166] isv.s 2 =10111  
     [0167] After A the OutputStateVector is, BoundVariable, TrueVariable and AnyMatch are initiallized to  
     [0168] osv.s 1 =0  
     [0169] osv.s 2 =0  
     [0170] BV=not (isv.s 1  and isv.s 2 )=not (11110 and 10111)  
     [0171]  =not 10110=01001  
     [0172] TV=BV and isv.s 2 =01001 and 10111=00001  
     [0173] AnyMatch=False  
     [0174] Referring to FIG. 6 ‘scanning of uncompressed terms’:  
     [0175] The following shows 631 and 632 at each iteration of the loop 629 to 632. 
     [0176]                                                      i = 1:               631)   TV = Formula.PIL[i] and BV               00001 = 11111 and 01001               00001 = 01001               False           i = 2           631)   TV = Formula.PIL[i] and BV               00001 = 10111 and 01001               00001 = 00001               True           632)   osv.s1 := osv.s1 or not Formula.PIL[i]               := 00000 or not 10111               := 01000               osv.s2 := osv.s2 or Formula.PIL[i]               := 00000 or 10111               := 10111           i = 3           631)   TV = Formula.PIL[i] and BV               00001 = 01111 and 01001               00001 = 01001               Flase                                                            
     [0177] Referring to FIG. 7 ‘scanning compressed terms’:  
     [0178] The loop from 734 to 737 is only executed once as the Compressed Possitive Index List only contains one element.  
                                                      736)   0 = (Formula.CPIL[i].s1 xor isv.s1) and               (Formula.CPIL[i].s2 xor isv.s2)               0 = (11111 xor 11110) and (00111 xor 10111)               0 = 00001 and 10000               0 = 00000               True           737)   osv.s1 := osv.s1 or Formula.CPIL[1].s1               := 01000 or 11111               := 11111               osv.s2 := osv.s2 or Formula.CPIL[1]s2               := 10111 or 00111               := 10111               AnyMatch := True                      
 
     [0179] Now because AnyMatch was assigned True, the test at (38) is passed, and the algorithm proceeds to (40) where CH is initialized to:  
     [0180] Referring to FIG. 8 ‘extracting information’:  
                                                      CH   := ((isv.s1 xor osv.s1) or (isv.s2 xor osv.s2))               and not BV           CH   := ((11110 xor 11111) or (10111 xor 10111)) and               not 01001               := (00001 or 00000) and 10110               := 00001 and 10110               := 00000                      
 
     [0181] After the loop from 844 to 848 no elements of the state vector are changed (deduced to either true or false). It is, however, verified that the state vector does not lead to any contradictions.  
     [0182] The invention may be embodied as a computer program or a part of a computer program, which may be loaded into the memory of a computer and executed therefrom. The computer program may be distributed by means of any data storage or data transmission medium. The storage media can be magnetic tape, optical disc, compact disc (CD or CD-ROM), mini-disc, hard disk, floppy disk, ferroelectric memory, electrically erasable programmable read only memory (EEPROM), flash memory, EPROM, read only memory (ROM), static random access memory (SRAM), dynamic random access memory (DRAM), ferromagnetic memory, optical storage, charge coupled devices, smart cards, etc. The transmission medium can be a network, e.g. a local area network (LAN), a wide area network (WAN), or any combination thereof, e.g. the Internet. The network may comprise wire and wire-less communication links. Via the network a software embodiment (i.e. a program) of the invention, or a part thereof, may be distributed by transferring a program via the network.