Title of Invention

A METHOD FOR GENERATING A DATABASE FOR CONFIGURING AND/OR OPTIMIZING A SYSTEM

Abstract The invention provides the ability to generate and use a database representing all solutions (legal combinations) satisfying all constraints of configuration problems on finite domains and/or intervals. The configuration space with all legal combinations is stored in a compact way in terms of nested arrays, where each legal Cartesian subspace has a unique index. Thus, the complete configuration space (which can be extended with object functions for optimization) is easily addressable by parallel indexing techniques and the database is therefore suitable for run-time applications (e.g. configuration on the Internet), which must be performed in real time.
Full Text 1 Background of the Invention
5 The aim of the invention is to support automatic modeling, analysis (verification) and real-time simulation of large-scale configuration problems on a standard computer (e.g. a per¬sonal computer). Mathematically speaking, such problems on finite domains or intervals can be expressed in terms of truth tables with combinations, each of which can assume either of the truth-values true or false (legal or non-legal). Here we are assuming N variables, each 10 with M elements. Thus, binary variables are to be considered as a special case with M=2.
Obviously, K^ combinations will cause "combinational explosion and it is therefore not a trivial task to solve large configuration problems with a multitude of variables. Nevertheless, the present invention makes it possible to unify the seemingly contradictory requirements for >5 completeness (all combinations must be accessible to ensure logical consistency) with com¬pactness of representation and speed of simulation.
For example, interlocking systems for railway operation are controlled by several thousands variables representing signal values or switch positions. To illustrate, even a small interlock-
20 in system with 2000 binary variables will be characterized by the huge number of 2^°°° states or combinations. Some combinations are legal (allowed), while other combinations are clearer illegal because they would cause disasters. To handle these systems with conven¬tional technology, it has been necessary to break down the system into subsystems of suffi¬ciently small size to allow their validation, whereby not only illegal, but also a large number of
25 legal combinations may be excluded, resulting in a less efficient utilization of the system. In general, the system variables will not be limited to binary values but will also include different data on finite domains (e.g. multi-valued logic, integers, or finite sets of intervals). It is highly desirable to be able to handle configuration problems in systems of that size by means of computerized tools which could provide complete and correct responses almost instant-
,30 onerously.
Another example is configuration of products or services (e.g. cars, computers or travels) on
the Internet. Many products are available in a multitude of variants, which must be selected
by the customer from a number of mutually dependent options. Thus, only some combine-
35 tions of these options are possible or legal, while other combinations are illegal due to some


technical or commercial constraints. It is therefore desirable to design e-commerce tools to enable the user to select interactively only the legal combinations, even from very complex product models.
While a number of computerized configuration tools have become available, e.g. the systems disclosed in WO 90/09001 and US 5,515,524 there is still a demand for systems which fulfill the requirements for completeness and compactness and speed of response. In this context, the term "completeness" indicates the mathematical requirement that all combinations have been verified to ensure logical consistency.
^J0
The present invention provides an elegant solution to this problem without the problem of "combinational explosion". As it will be understood from the following description, the crux of the invention is the establishment of a novel type of database, in the following tanned an "ar¬ray database". While the database is an optimal tool for the complex configuration problems indicated above and described in greater in the following, it will be understood that due to its unique inherent advantages, it is also useful for a wide range of applications for which con¬ventional database systems, typically relational databases, are used at present.
/
A scientific/mathematical discussion of principles relevant to the invention is given in Mailer, 20 Gert L.; On the Technology of Array-based Logic. Ph.D. thesis. Electric Power Engineering Department, Technical University of Denmark, January 1995.

2 Brief Disclosure of the Invention
In one aspect, the invention relates to a method for generating a database useful for config¬uring and/or optimizing a system spanned by variables on finite domains and/or intervals, 5 said method comprising generating and storing, in a memory or storage "medium of a com¬puter, an addressable configuration space of the entire system in terms of all legal Cartesian subspaces of states or combinations satisfying the conjunction of substantially all system constraints on all variables, with all interconnected legal Cartesian subspaces being ad¬dressable as legal combinations of indices of link variables, so as to establish a database in 10 which substantially all legal solutions in the system are stored as nested arrays.
In the following, the database generated according to the invention will be termed an "aoay database", this term reflecting the fact that all legal solutions are stored in the database as one or more nested arrays. 15
Definitions and explanations relevant to some of the terms used in the present specification and claims are as follows:
"Configuring" means establishing substantially all legal combinations of the variables
20 satisfying substantially all the constraints on the system. Preferably, ail legal combi-
nations of the variables satisfying all the constraints on the system are established, in which preferred case the legal Cartesian subspaces of states or combinations will satisfy" the conjunction of all system constraints on all interconnected variables.
25 "Optimizing" means applying a heuristic selection of combinations within a set of legal
combinations.
The term "a system spanned by variables on finite domains and/or intervals" indicates
that each variable of the system consists of a finite set of elements or state values
30 (e.g., logical truth values) or a finite set of intervals.
The term "An addressable configuration space" indicates that substantially ail legal combinations are explicitly represented; in the preferred case, all legal combinations are explicitly represented. 35
f

"A Cartesian subspace" is a compaci represtJiudLiwu ui wuc w. n,^,^ icua. v-umuina-tions, all combinations being derivable/calculated/ as the Cartesian product of frie elements or state values for each variable.
5 "System constraints" are the relations {prepositional functions) on variables defined
for the system.
"Interconnecting variables" indicates variables present in at least two relations.
10 "A link variable" means a variable generated by the method according to the invention
and added to a given relation with a unique index which identifies one Cartesian sub-space.
"Interconnected legal Cartesian subspaces" means legal Cartesian subspaces with at
15 least one common variable.
It is a crucial feature of the invention that all illegal states or combinations violating the sys¬tem constraints are excluded from the relations. Such exclusion of illegal states or combina¬tions can preferably be performed while the database is generated by the method according
20 to the invention, the illegal states or combinations being excluded whenever identified. A state of contradiction or inconsistency is present in a system if just one relation of the system has no legal combination or state. On the other hand, a system is said to be consistent if at least one state or combination is legal, i.e. satisfying all system constraints, if, in the genera¬tion of the database, just one relation of a system is found to have no legal combination or
25 state, then that whole system is in a state of contradiction or inconsistency and must be ex¬cluded.
In the following, the process of colligating relations (that is, combining relations to arrive at a more complex subsystem or system) is discussed in greater detail, it will be understood that 30 on each level of the colligation process, inconsistencies or contradictions will be identified and will, thus, result in exclusion of the colligated subsystem or system. Thus, when the gen¬erating process has been completed, the system will be consistent, as manifested by all rela¬tions having at least one legal Cartesian subspace.
35 In the present specification and claims, the term "system" is used about an entire system of variables or, alternatively, about a part of an entire system of variables. In ail cases relevant to the present invention, the system, understood in this manner, is completely defined in that

every combination under the system is either legal or illegal with respect to all system con¬straints relevant to the use of the database and preferably with respect to absolutely all sys¬tem constraints. Thus, the term system, used about an entire system of variables, indicates, in the context of the claims and the specification, that the entire system is completely defined
5 with respect to all system constraints relevant to the use of the database, and preferably vi"ith respect to absolutely all system constraints. When a system of variables is not completely defined in the above sense of this term, then only that part of the system which is in fact completely defined is covered by the tern "system" as used in the claims. The term "substan¬tially", as used in claim 1, indicates that it is possible to have a system which is not defined
10 with respect to system constraints that are not relevant to the use of the database. The them "substantially" can also indicate a system in which the process of colligation has not been completed, and where the njntime environment must be adapted to perform certain tests for consistency. While the latter variant is not considered ideal, it may nevertheless apply for certain applications of the invention where the realtime capability of the njntime environment
15 is not a requirement.
As indicated above, the system constraints may be determined by conjugating one or more relations, each relation representing the legal Cartesian subspaces of states or combinations on a given subset of variables. The conjugation of the one or more relations comprises cal-20 culating the Cartesian subspaces satisfying the combined constraints of the one or more re¬lations. If no relations have common variables, no further action is required to conjugate the relations.
According to an important preferred feature of the invention, all relations with at least one 25 common variable are colligated. The colligation comprises conjugating the constraints of two or more relations being connected by having common variables to establish the Cartesian subspace(s) satisfying the combined constraints of the two or more relations.
The colligation of the two or more relations will normally be performed by joining the two or 30 more relations up to a predetermined limit. Joining comprises the operation of replacing a set of relations with a single relation satisfying the combined constraints of the set.
The set of relations is not limited to two relations but can in general be any finite number of relations. In a preferred embodiment of the invention the case where three or more relations 35 are joined is typically decomposed into a number of pairwise joins. This pairwise joining can comprise a predetermined strategy or the joining can be in a random order.

10
15
20

The joining process will typically reduce the number of relations, and the resulting number of relations are then colligated by linking them and grouping them into one or more cluster(s) of relation(s).
A cluster can comprise one relation or a set of interconnected relations. These clusters will be described in greater detail in the following.
The linking of the relations consists of adding link variables and adding one or more calcu¬lated relation(s) representing the constraints on the link variables.
The linking of relations can be within a cluster or between dusters. The linking between two clusters may be performed by establishing a link relation comprising two link variables, while for a linking within a cluster the link relation(s) comprises all link variables on the relations in the duster.
If three or more relations interconnected with common variables are generating cycles or closed paths, then they are grouped into a single cluster comprising the three or more rela¬tions. As a consequence the resulting duster(s) are interconnected without cycles, i.e. in a tree structure.
The tree structure makes it possible to ensure completeness of deduction in the run time en¬vironment by state propagation, for example when a configuration or optimization is per¬formed.

25 The term "completeness of deduction" indicates that all logical consequences must be de¬duced on one or more variables. In important embodiments of the invention, the complete¬ness of deduction relates to all logical consequences on all variables, but as indicated above, the invention is not limited to that.
30 When the amay database is to be used for optimization, one or more object functions are in¬corporated. An object function of a given subset of variables, the object function deriving characteristics of the given subset of variables, is linked to the complete configuration space by dedudng the constraints imposed by the object function on each link variable connected to the given subset of variables.
35

After ttie array database has been generated by the method according to the invention, ob¬ject functions can provide information between a set of variables and a set of object function values, e.g., price, weight, color.
5 If a set of object function values does not have a "natural" order, e.g. as numbers, an arbi¬trary order can be assigned to the set of object function values.
The characteristics of the object function may be determined and the constraints on the link variables deduced on each combination of the given variables, the result being represented as a relation on the object function, the given variables, and the link variables.
10
These characteristics can be the values of the object function given by functional mapping of a set of independent variables or a set of constrained variables. The mapping can also be a general relation yielding one or more object function values for each combination of the vari-15 ables.
In another aspect, the invention relates to a method for configuring and/or optimizing a sys¬tem spanned by variables on finite domains, said method comprising
20 - providing a database in which substantially all legal solutions in the system are stored as nested an^ys and
deducing any subspace, corresponding to an input statement and/or inquiry, of states or combinations spanned by one or more variables of the system represented by the nested arrays by deriving the consequences of a statement and/or an inquiry by applying the
25 constraints defined by the statement and/or inquir/ to the database,
"Deducing" means deriving or determining ail logical inferences or conclusions from a given set of premises, i.e. all the system constraints.
30 "Inquiry" means a question for which the array database can provide all answers.
A question could be about the legal combination(s) of a given set of variables satisfying the system constraints and possibly also satisfying an external statement.
35 An external statement can be a number of asserted and/or measured states and/or con¬straints from the environment.

Thus, a deduction of any subspace of states or combinations is performed on a given subset of variable(s) either without or colligated with asserted and/or measured states and/or con¬straints from the environment.
5 The interaction between the system represented by the array database and the environment is suitably performed by means of a state vector (SV) representing all legal states or values of each variable.
Thus, an input state vector (SV1) may represent the asserted and/or measured states from 10 the environment, while.an output state vector (SV2) may represents deduced conse-quence(s) on each variable of the entire system when the constraints of SV1 are colligated with all system constraints in the array database.
The deduction can be performed by consulting one or more re!ation(s) and/or one or more 15 object function(s) at a time by colligating the given subset of variables in the relation with the given subsets of states in the state vector and then deducing the possible states of each variable.
The consultation of a relation can be performed by colligating, e.g. joining, the relation and 20 the states of the variables present in the relation. The result of the consultation can be the projection (union of all elements) on each variable of the colligated relation, or the result can be the colligated relation. The colligation can of course be a joining, but it should be evident from the discussion given herein that the consultation of each relation is not limited thereto.
25 In a preferred embodiment of the invention two or more variables, are colligated in parallel; the projection on two or more variables can simiiariy be performed in parallel. The invention is not limited to such parallel implementation, and the invention can just as well be imple¬mented sequentially.
30 In one embodiment of the invention completeness of deduction is obtained by consulting connected relations, until no further consequences can be deduced on any link variable. This operation is termed "state propagation". Such state propagation comprises consulting two or more relations in parallel. The invention is of course not limited to such parallel implementa¬tion, and, due to the cluster structure, the invention can just as well be implemented sequen-
35 tially.
1

An important feature of the configuration and/or optimization according to the invention is that the state of contradiction can be identified, when no legal states or values are deduced when consulting at least one relation.
3 Figures
5 In the following the invention will be described in greater detail with referen"ce to the figures: Fig. 1 Modeling an array database
Fig. 2 Array database simulation (state deduction)
Fig. 3 Compilation of variables and relations
Fig. 4 Colligation
10 Fig. 5 Strategy for joining a list of relations
Fig. 6 Colligation graph of relations
Fig. 7 Colligation graph of clusters (tree)
Fig. 8 Directed colligation graph of connected functions (input-output dataflow)
Fig. 9 Colligating relations in a cluster
15 Fig. 10 Cycle elimination yielding a tree structure of colligated relations
Fig. 11 Determination of run-time cluster with added system relations
Fig. 12 Linking clusters by colligating connected relations •
Fig. 13 Colligation of relation pair by projection on link variables
Fig. 14 Linking an object function to the configuration space
20 Fig. 15 The state deduction on a single cluster
Fig. 16 State propagation on interconnected clusters (acyclic connection of rela¬tions)
Fig. 17 Combinational logic network
25
10

Fig. 18 User interface example Fig. 19 User interface example
4 Summary of the Following Disclosure
The array database (to be temned ADB in the following) is a compact, yet complete repre¬sentation of all legal combinations of configuration problems on finite domains or intervals. The configuration space of legal states or combinations is represented geometrically in terms of nested data an-ays, and the ADB can be simulated very efficiently by simple operations on these aoays. Each step in the process ofyADS modeling and simulation is explained in the Chapters 5 and 6, respectively.
10
The major data flow of ADB modeling is summarized in Fig. 1. Input is a user-defined speci¬fication of the system constraints in tenns of a set of rules or relations on a given set of vari¬ables. The ADB is modeled in a three-step procedure as sketched in the process block ADB-MODELinFig. 1.
15
1. Compile variables and relations (Chapter 5.1):
Each user-defined variable and each relation is compiled into the internal an-ay repre¬sentation. At this stage, the relations are considered as independent items.
20 2. Colligate relations, verify system (Chapter 5.2):
The configuration space of the entire system is determined by colligating interconnec-tected relations (constraint elimination). The system is simultaneously tested for logical consistency and redundancy.
25 3. Generate object functions (Chapter 5.3):
Optionally, the relations may be extended with further attributes, when the legal combina¬tions satisfying the system constraints are associated with values or object functions to be optimized like, say, a price or a weight.
30 At this stage, the process of ADB modeling is finished. The entire configuration space can now be addressed by coordinate indexing and other simple operations on the nested arrays.
The major operation of ADB simulation is sketched in Fig. 2 and will be described in more detail in Chapter 6.
//

Each item of the state vector SV represents the state (the legal values) of the associated variable, in the input state vector SV1, one or more variables are bounded due to external measurements or assertions. SV2 represents the resulting constraints on all variables. An important technological requirement is completeness of deduction; that is, a// constraints on 5 the variables in the output state vector must be deduced.
The most important technological novelty of the ADB can be summarized as follows:
1. ADB simulation is performed with completeness of deduction in real-time - with predict-
10 able use of processing time and memory. TTie ADB simulation is therefore suitable for
embedded configuration or control systems and performs well on small computers.
2. A precondition for (1) is that all relations are colligated before simulation and that the
configuration space of the entire system is represented geometrically in tenms of nested
arrays. The entire system is automatically tested for logical consistency (verification).
15 ADB modeling is not a real-time task. On large systems, the modeling process can with
advantage be computed on a dedicated modeling server with multiple processors.
3. One common representation of all system constraints (the standard array fonn of rela¬
tions) unifies prepositional logic, predicate logic (multi-valued logic) and relational alge¬
bra.
20 4. All processing on the standard array form (ADB modeling and simulation) is based on a few fundamental an-ay operations, all of which are suitable for parallel processing.
The different rule-based systems on the market today are representing rules or relations as independent items (no colligation). Thus, these njles must be manipulated individually by 25 search rather than simple geometrical operations on arrays. Processing time therefore de¬pends on the extent of search, which is a problem in applications where completeness of de¬duction must be ensured in real-time (e.g. railway interiocking systems).
5 ADB Modeling
Basically, the task of ADB modeling is constraint elimination; that is, all non-legai combina-30 tions must be eliminated yielding an explicit representation of all legal combinations or legal Cartesian subspaces.
5,1 Compile Variables and Relations
Input is the user-defined system constraints in terms of variables (on different data types or scales of measurement) and mles or relations on these variables. The compilation is a two r^5 steo procedure as shown in Fig. 3.
/2.

5.1.1 Compile the Domain of Variables
The domain of each variable is any ordered finite set (a lis:) withn unique items. The domain {False, True} of a propositionai variable is thus a soeda; case with n=2. The list may be an explicit representation of all elements in a finite domain, or, in the case of large or maybe even infinite numerical domains, an ordered set of disjoint intervals.
As an example, we will consider the global domain of a system with six different state vari¬ables illustrated in Table 1.

Array representation
index State variable - Domain
0 A {False True} 0 1
1 WlDTH(x) {14 5} 1 1 4 5
2 LENGTH(x) {2 4 6 8} 12 4 6 6
3 ALARM {Off On} 1 0 1
4 COLOUR(x) {Red Yellow Green Blue} 0 12 3
5 TEMP(x) {x e R 1 11 100} ,



i j t




1 I




ijo ijii 30i i 11 1 1 11 n 1 0||100||
11 II




i 1
1 1 1 ■ " "
1












10

Table 1 Domain of system with six state variables

A and ALARM are propositionai variables with the length n=2, while COLOUR(x) is a predi¬cate variable representing a nominal scale measurement vmh n=4. In the internal array rep¬resentation, each measurement is given by its assoaated domain index. LENGTH(x) and 15 WlDTH(x) are simple ordinal scale measurements with an explicit representation of all do¬main elements, while TEMP(x) illustrates an interval scaie measurement given by a finite set of intervals. An interval is defined by its lower and upper boundary given by the value and type of each boundary (O=open, 1=dosed).
5.1.2 Compile Each Relation into Standard Array Form
20 Each user-defined relation on a subset of domain variables is compiled into \he standard ar¬ray form, which is a nested array with two items. The first item is the set of legal Cartesian subspaces, while the second item is the domain indices of the associated state variables. All the succeeding processing on the relations is based on this common representation, which may be conceived as the basic ccmponent of the ADB.
13

10

EXAMPLE
Given the following reiation on the variables V^IDTH and LENGTH in Table 1:
R: WIDTH is less than LENGTH
That is, the complete state space of legal and non-iegai combinations is:
R: 2 4 6 8 (LENGTH)
1 i
1 |1 1 I 1|
4 |0 0 i ij
5 |0 0 1 ij (WIDTH) I "
Table 2

15 The standard array form of Table 2 is depicted below as tables in two isomorphic forms Vi"ith eight legal combinations {expanded form) or, altemaiiveiy, two legal Cartesian subspaces {compressed form):

WIDTH TiKNG"IH." i
1 2
1 4
1 6
1 8
4 6
4 8
5 6
5 B
a) Expanded


KIDTH " lEBHSEH.
1 2 4 6 8
4 5 6 8
b) Compressed



20
25

Table 3
EXAMPLE
The compiled array form of the reiation TEMP (>120) =» ALAPJ^. on the domain in Table 1 is:
/^

TKMP

ALfiBM



1 1 1
1lO ijll 30| II 1 1 1 ! 1
li i|ico :-;:i 1 1 1 j
1 1

0 1

1 I n
0 oj|120|I

! L

J

Table 4
5.2 Colligate Relations
5 Mathematically speaking, the constraints of the entire rystem are the conjunction of all rela¬tions. So far, during compilation, we have considerec the user-defined relations as inde¬pendent items. Tne configuration space of tns complete system is now computed by colli¬gating the interconnected relations (elimination of the connectivity constraints).
10 Simultaneously, the system is tested for logical consistency: when a local configuration space is empty, the conjunction of all system constraints yields a contradiction. Moreover, redundant and non-constrained information is eriminatsc autom.atically.

15
20

The procedure shown in Fig. 4 is adopted.
5.2.1 Join Relations until Size Limit
The simplest operation of colligation is to join relation pairs with common variables into single relations representing the conjunction of the pair. Connected relations are joined whenever convenient; that is. when the size of the joined result is less than a given limit. When two re¬lations have many common variables, the joined relation will be smaller than the arguments. Similarly, when the relations are sparsely connected, the joined relation may blow up in size. In the case of contradiction (logical inconsistency), the configuration space of the joined reja-tion is empty. Isolated (non-connecting) variables without importance for the system simuia-t,^r^ /jntQi-im v/ariahips^ mav bs eliminated.

/r

The strategy for joining a list of relations is shown in Fig. 5. Tns)o/>7 factor or connectivity factor of a relation pair is used to predict the size of the joined result . The join factor of a connected pair is defined as follows:
/,x/,x(^x(l + lnV, ))x(^,xa + ln^"/))
JF^ i4 ^^^^
where:

10

/,: number of isolated variables in relation /
Af-. size of relation / (number of Cartesian subspaces)
T-. size of relation / (number of tuples (combinations))
C: number of common variables + number of common interim variables

15 EXAMPLE
Given the small system with t^x8e relations RO, R1, R2:

20


RO (A V E) => (C V D)
Rl C => E A F
R2 D =:> E A G

Table 5
The compilation of each relation yields:

RO

Rl

R2





0 1 0 0 I 0
0 1 0 1 1 0 1 1 1
0 1 0 1 1 1 0

0 I 0 1 I 0 1
11 1 rT~



25

Table 6

The relations in Table 6 may be joined into a single relation R = RO A R1 /\ R2 representing the complete configuration space:
/6

R = join RO Rl ?_2

0 0 1 0 0 1 0 1 i 0 1 0 1
0 1 0 1 1 0 1 1 1 10 1 1
0 1 0 1 1 1 1 1 i 1 1 1
0 1 0 1 1 1 0 1 1 1 1 1 0 1
Table 7
We have thus finished the colligation task on this small example; all constraints of the iso¬lated relations as well as the connectivity constraints are represented in the joined relation. 5 The result of modeling the system is thus an array database with the single relation depicted in Table 7.
#
In general, the array database will contain more than a single relation, when systems scale
10 up.
5.2.2 Group Relations into Clusters
At this stage, it is not possible to join further relations v/ithin the user-denned size limit. The colligation strategy now depends on the properties of the colligation graph depicting the 15 structure of interconnected relations. The relations are represented by the nodes, while an arc linking two nodes (relations) represents the common variables.
Two different kinds of graphs are particular imponanr
20 • Trees (graphs without closed paths or cycles): In this case it is possible on ensure com¬pleteness of deduction by state propagation on the simple links between the relations. Example:

25


RO: A => (3 V C)
Rl: (3 V C) => D

\T] (BC)--p~[



30

Table 8
• Graphs with closed paths or cycles: The cycles must be eliminated to ensure complete¬ness of deduction by simple state propagation. Example:
J7

RO (A V E) =:. (C V D)
Rl C =:> E A F
R2 D => E A G
(C)" "(0)
Table 9
5 Before further colligation, the relations are grouped into clusters, all of which can be linked together without cycles. When the colligation graph of relations is a tree, each relation is thus associated with a single duster.
Fig. 6 illustrates the colligation graph of a given system. Of course, we may eliminate all cy-10 cles by grouping the relations into a single duster. However, in order to make the succeeding colligation process most efficient on large systems, it is desirable to group the relations into the maximum number of clusters. In this example, the maximum number of clusters is four as shown in Fig. 7.
15 In the case of input-output systems, each relation is a function (output = f(input)). The prede¬fined flow of data from input nodes to output nodes is depicted in ^directed colligation grapfi. When the graph is acyclic (no cydes or strong components), the data flow is complete by a simple state propagation from input to output. In the case of a cyclic digraph, the cydes must be eliminated by grouping the associated relations (functions) into clusters as shown above.
20
Fig. 8 illustrates a predefined dataflow on the syste.m LnRg. 5 assuming that each relation is a function. We note that the graph is acyclic and the fiow is thus complete with a state propagation from RO to R15.
25 5.2.3 Colligate Relations in Each Cluster
The major steps are sketched in Hg. 9. In order to ensure completeness of deduction, all cydes in the cluster must be eliminated (Fig. 9.1). Tne nested run-time cluster (Fig. 9.2) is an altemative compact and eifident representation of the duster configuration space.
30 5.2.3.1 Cycle Elimination: Determine Tree Structure of Colligated Relations (Fig. 9.1)
When a list of relations dosing one or more cydes in a duster are large and sparsely con¬nected, the "combinational explosion" will make it impossible to join the list into a single rela-
/^

lion. Therefore, we will generate an equivalent but mucr. more compact list of colligated sub-spaces; that is, a new list of relations with the following cha3cieristics:
• Each user-defined variable (domain variable) is onry p-resent in a single relation.
5 • The relations are linked together by system generated link vanabies yielding a tree structure (without cycles).
• Each local Cartesian subspace of legal combinations is associated with a unique link
variable with a unique index.
10 Thus, we will isolate variables present in a single relation and perform the coiiigation only on subspaces with common variables. The five-step procedure shown in Fig. 10 can be used on any set of relations, even when the coiiigation graph is acyciic.
EXAMPLE
15
Given the cluster relations RO, R1, R2 closing a single cycle:

RO (A V 3) ::o (C V D)
Rl C => S
R2 D => E



Table 10
20 The standard array form of each compiled relation is:



Rl
RO 0 1 0 0 0
0 1 1 0 1 0 1 1
0 1 1 0 1 1 0

0 t 0 1 I

Table 11
List of relation(s) on isolated (non-connecting) variables (Rg. 10.1 and Fig. 10.2):
IiinkQ.
0 0 - 0
0 1 0 1 1
0 10 1 2

25

Table 12

/9

List of relations on connecting variables (Fig. 10.1):


T.-i nVn
_0 0 0
0 1 1 I 1
10 2


0(011
111!

Table 13
When the list of relations on connecting variables is joined (Fig. 10.4), we have the following result with two relations on isolated domain variables and one common linl T.inTrn
0 1 0 0
0 1 i 0 1 1 2

c D E LinTfO
I^H
EB HjjQB
oa B ■EH ^■^M
HDI wm HDH HEHI

10

Table 14

#

15

The tree structure of colligated relation fulfills the requirements for completeness, compact¬ness, and speed of simulation. Completeness of deduction is ensured by state propagation on the relations in the tree (see Section 0). The nested duster representation to be intro¬duced in the following is an alternative (isomorphic) representation.

Sometimes the user-defined relations are including internal system variables (interim vari¬ables), which can be eliminated. An example is network problems with input and output 20 nodes (which are connected to the environment) and a number of internal nodes connecting input and output nodes. When the network constraints are represented in the ADB, it is de¬sirable to eliminate the internal variables and to represent only the subspaces on the input-output variables.
^0

5.2.3.2 Determine Nested Run-time Cluster (Optionally)
The aim of the following task is to determine a very corrpac: rjn-time cluster representation, 5 which can be simulated by simple coordinate indexing and table look-up without state propa¬gation - even on small scale computers and controllers like, say, electronic relays.
The run-time cluster consists of the original domain relations extended with link variables ad¬dressing the Cartesian subspaces, and a set of system relations representing the relations 10 between link variables. The impact of each Cartesian subspace on the entire system is de¬termined by asserting the associated link variable index and then deducing the state of each link variable. This deduction is for example carried out by state deductions on each link vari¬able index. Tne state deductions may be executed in parallel.
15 The determination of the nested njn-time cluster is shown in Fig. 11.
EXAMPLE
20 Let us again consider the cluster Table 10 with three relations RO, Ri, R2 :
The run-time cluster depicted below consists of the three domain relations (left row) and the three associated system relations (right row). For example, in system relation 0, the three indices of link variable LinkO (representing the Cartesian subspaces of RO) is used as the 25 input to deduce the constraints on each link variable. Tnus. system relation 0 represents the impact of the Cartesian subspaces in RO on the entire system.
2-i

iyscem relation 0

r 0 0 0 0 0
toi 0 1 0 1 1 1
01 0 1 1 0 2


LinkO Link!. LinkZ
0 0 1 0 1
" 1 1 1
2 1 1




0 0 : 0
oil 1

System relation 1
LinkO Linkl. LinkZ
0 ■ O" 0
0 12 1 1



R2

System relation 2


i^ 1^ LmkZ LinkO Lmkl LirJc2
0 0 -O--:;: 0 0 0
0 1 1 1
0 12 1 1
Table 15
5J2.4 Unk Clusters
Wi| have now finished colligation of the relation(s) in each duster, and the final step in the process of colligation is to colligate all relation pairs, which are connecting clusters. For ex¬ample, In the system sketched in Fig. 7 the relation pairs (3dosa»o 3tjus,c,i). (9 10) and {10 12) must be colligated.
;7^edata flow of linking clusters is shown in Fig. 12.
jThe result of colligating a relation pair is a new relation (to t>e termed/;n/c relation in the fol¬lowing) on the common variables and the two link variables. When the set of link relations is added to the array database, it is possible to ensure completeness of deduction by state propagation on the clusters and the link relations.
Fig. 13 illustrates in more detail the colligation of each relation pair {Fig. 13.2).
99

EXAMPLE
Given the relation pairf?0, R1:

RO: (A V B) => (C V D)
Rl: (C V D) => (£ A F)
Table 16
Obviously, the simplest way to colligate these simple relations is to join the pair into a single:
10

0 1 0 1 0 0 0 1 i 0 1
0 1 1 0 1 p 1 1 1 1 1
0 1 1 0 1 1 0 1 1 1 1
Table 17
However, to iiiustrate the isomorphic form of link relations, we will extend the standard array form of RO, R1 with link variables:

RO: (A V B) => (C v D)

0 0 0 0 0
0 1 0 1 0 1 1 1 1
0 1 0 1 1 0 2

Rl: (C V D)

(^

T.-rnVT

0 0 0 1 0 0
0 0 0 1 1
0 1 0 1 1 1 2
15 Table 18
Colligating the subspaces on the common variables C, D yields the following link relation:
Link relation: RO Rl
T.-inkO linkl
0 0 0 1 0 1 2
0 1 1 1..- 1 2
1 0 2 t 2
Table 19
Z3>

in addition to the argument relations R0,R1 the lini #
5 5.3 Add Object Functions (Optionally)
The configuration space of legal combinations may be extended with user-defined object functions to be manipulated heuristically, e.g. a fuzzy value (for fuzzy logic computations), a weight or a price (for optimization).
10 An object function O is defined on a subset on the state variables So, S,,...Sn: O = f(So, Su...S„) and is compiled irito standard array fonm.
EXAMPLE
15 Given a system model with the configuration space fVV/DTl-/. LENGTH) and the object func¬tion PRIZE = f (WIDTH, LENGTH) represented in a single relaDon in standard array form:
WIDTH LEHGTH"

1 2 2,5
1 4 4.0
1 6 3.3
1 8 8.4
4 6 20.2
A 8 50.0
5 6 14.Q
5 8 17.2
Table 20
20 When the object function is to be optimized during system simulation, we may also represent the configuration space of large domains in terms of Cartesian subspaces on which the ob¬ject function is monotonic:
a-i^

■J 1
WI"Vi"H T-"-"-N""!^"^
1
2 4
6 8
5 4
6 8


en I "M
r2.5 4.C1
[5.3 e.4:
[14.0

Table 21

The object function of each Cartesian subspace is given by an interval With the lower and upper boundary, and the associated state variables are ordered to make the object function 5 increasing.
#
The object function may be linked to the configuration space in either of two ways:
10 1. If the configuration space of the state variables So. S,,...S„ is represented in a single rela¬tion (in standard array form), the relation may be extended with a further attributeO rep¬resenting the object function. This is to be considered as a special case as shown in
15
Table 3. 2. in general, it is more convenient to add the object funcnon as a new relation in standard array form on the attributes O.So, Su.Sn and the link ^-a.■iabies associated with the con-figuration space of Sa Su—Sn ■
The flow chart of adding object functions is shown in Fig. 14.
^^"

EXAMPLE
Given the following configuration space in terms of three reianons:
RO

A B 0 0 T.inTrn
0 1 0
0 0-
0 1 1 0 1 0 1 1 1
0 1 0 1 1 0 2

0 1 0 1 0 1 0 0
0 1 0 1 0 1 1
0 1 1 0 1 1 \ 1 2
LinkO .-: T.inlcl
_0 0 0 0 12
0 1 I 1 I 1 I 2~
10 2 t 2
Table 22
10 The object function Y = f(B,E) is added to the an-ay database by a projection on all link vari¬ables associated with the state variables B,E:
y = f(3,H)


0 Q ^
0 12 1 0~2 12 1 2


15

Table 23
6 ADB Simulation
When the modeling task is finished, the anray database is prepared for a very efficient simu¬lation, which can be performed in real time. The major operation for ADB simulation is the state deduction shown in Fk:. 2.
Z6

The state vector represents the state (the legal vai"jes) o: eacn state vanaoie. in the input state vector SV1, one or more variables are bounded due to exiemai measurements or as¬sertions. Tne deduced state vector SV2 represents the resulung constraints on all variables, when the system constraints and the constraints of the input state vector are colligated.

10

The state deduction is carried out by means of a few array operations (suitable for parallel processing) on the basic components of the array database;
• the relations,
• the relation cJuste,"^,
• the interconnected (linked) relation dusters, and
• the linked obiect functions



15

6.1 The State Deduction on a Single Relation
The state deduction on a single relation in standard array form is carried out by colligating (by intersection) the input state vector (SV1) with the reiation succeded by a projection on each variable of the relation yielding the output state veaor (SV2). The colligation and pro¬jection are described in greater details below.

20 EXAMPLE
To illustrate, we will again consider the system with the relations RO, R1, R2:

25


RO: (A V B) => (C > ij ■
Rl: C => E
R2: D => E

Table 24
Modeling the system into a single relation (by joining RO, Rl, R2) yields:

0 0 0 1 0 1 0 1
0 1 0 1 0 1 1 1 1 1
0 1 0 1 1 1 0 1 1
Table 25
30 We will now deduce all consequences of the external measurement-4=f (true). The following three-step procedure is adopted:
2J

1. Identify all bounded variables in the input state vector SV1.
A is bounded or constrained to ^, while the other variables are unbounded and thus as¬signed all the possible domain values (0 1). The input state vecior SV? is therefore:
0 1 0 1 I 0 1 ! 0 1

10

A B C D £
Table 26
Colligate the constraints of the relation and the input state vector SV1. Each Cartesian subspace in the relation is intersected withSVt item by item (variable by variable). The most efficient operation is to select only the bounded input variables and to compute the intersection axis by axis (suitable for parallel processing if desired). Non-valid (empty) Cartesian subspaces are deleted. In the present example, only the first Cartesian subspace is empty and therefore deleted:


r - -
1 0 1 0 1 1 i 1 ;
1 0 1 1 0 1 1 ^

15

Table 27
3. The output state vector SV2 is the projection (union of all elements) on each axis. This operation is also suitable for parallel processing on each axis. The axis projection on Table 27 yields the following output state vector S\/2
0 1 I 0 1 I 0 1
A 3 C D
Table 28
We conclude that -A=£=1, while the other variables are unbounded (don"t care or tautology).
20 #
This basic state deduction on a single relation is the foundation for state deduction on rela¬tion clusters and interconnected clusters. Moreover, it should be noted that this operation can be used on any data type (scale of measurement) on any relation in standard array form, in-25 eluding object functions. In the case of object functions, the input state vector may be con¬strained by optimization criteria like, say, the minimum prize of a given configuration.
X^%

6.2 The State Deduction on a Nested Relation Cluster
Tne structure of the nested njn-time cluster with domain rerations and system relations on common link variables was introduced previously (modeling step 2.3.2). The state of the cluster can be deduced very efficiently in a five-step proceaure snown in Fig. 15.
The key to the efficient state deduction is that each Cartesian subspace in the complete con¬figuration space has a unique projection on the link variables, which can be deduced (Fig. 15.1 -Fig. 15.2) and then indexed (Fig. 15.4 -Fig. 15.5) one-by-one or in parallel. No heu¬ristic search is used in this process.
10
The identification of txounded input variables (Fig. 15.1) is used to select those domain rela¬tions, which are candidates to be consulted (there is no reason to consult domain relations only with unbounded variables - these relations will not deduce further constraints on the state vector). However, step (Fig. 15.1) is not essential; all domain relations may be chosen 15 as candidates for the succeeding step (Fig. 15,2). The domain relations (Fig. 15.2) may be consulted one-by-one or in parallel yielding a local output state vector, presumably with new constraints on some variables. If the link variables are still unoounded, the state deduction is completed (Fig. 15.3).
20 If some link variables are bounded, the impact on the complete duster is deduced by con¬sulting the system relations (Fig. 15.4) (one-by-one or in parallel).
Finally, the complete impact on the domain variables is deduced by consulting all domain relations with new constraints on the associated link variables (Fig. 15.5). The result is the 25 complete output state vector.
Summing up, parallel processing may be introduced at different levels:
1. Parallel colligation (intersection) of each axis in the individual relations.
2. Parallel projection on each axis in the individual relations. 30 3. Parallel state deduction on domain relations (10.2).

4. Parallel state deduction on system relations (10.4).
5. Parallel state deduction on domain relations (10.5).
EXAMPLE
35
Given the nested duster representation of the follovirtng system:
^7

RO

0 0 0 0 1 0
0 1 0 1 0 1 11 1
0 1 0 1 1 0 1 2
Rl
Linkl-
0 ( 0 0
oil 1



Sysce K. r=lat: . en 0


.T.inTcQ. T.inTcT T.inlr?
■ 0 0 1 1 G 1
■ 1 1 ! J.
2 1 1 1

System reiat: .on 1
T.inkO Tiinlcl T.iTilr?
0 0 1 0
0 12 1 1 1

System relation 2
LiEkO- T.-inVI T.iTiTr?
0 0 1 0
0 12 1 i 1



10

Table 29
Moreover, given an input state vector SV"/. The state dedU"Ction on the cluster is earned out as illustrated in Fig. 15:
1. Identify bounded domain variables in the input state vector (Fig. 15.1)
Only variable A is bounded:
SVl:



T.i ■
Oli01|01|01 10 12 1 CI
A B C D £

0 1
.ink2

Table 30

15

2. Consult all domain relations with bounded domain variables (Fig. 15.2)
RO is the only domain relation on the bounded variable A Tnus; there is no reason to consult R1 and R2. Consulting RO yields a local output state vector v/ith new constraints on LlnkO:

30

ConjuncTiion RO A SVl:

^ B c D Linka
r

A n
t~ - - "
1 0 1 0 1 1 1
1 0 1 1 0 2
Local output SV:

0 1 0 10 10 1


0 1
0 1
LinkO Linkl Lir.k.2 Table 31

5 3. Consult ail system relations associated with bounded link variables (Fig. 15.4)
system rel.O A SV:

LjJikO Linkl ^ T.-infr?
r\ ■* 1 r> 1
- 1 "- -
1 1 1 1 =D
2 X 1 1
Local outDur SV:
as 0 1 1 0 1 1 0 1 1 0 1 1

^lliar:^:-,".^;-!
LinkO Linkl Lir.Jc2

Table 32
10 4. Consult all domain relations with bounded link variables {Fig. 15.5)
The domain reiations associated with bounded link variables are consulted yielding the global output state vector SV2:
Rl A SV:

c E T-T^M
^■■SHB
Immg ■BH ^^^K^^^H
KH9 a ■BH

15

Local outDUt SV:
0 1 I 0 1 I 0 1
A 5 C D


IL:L 1-2Z
LinkO Linkl Link2

Table 33
3J

R2 A SV:

1
(
0 1 1 1 1

SV2:
0 1 I 0 1 I 0 1
A B C D

£ LinkO Linkl Link2

Table 34

10
15

6.3 State Propagation
State deduction on interconnected clusters is carried out by state propagation as shown in Rg. IS. All duster relations with bounded variables are consulted and the state vector up¬dated repeatedly, until no further information can be deduced. In practice, the propagation is controlled by the link variables: when no further constraints can be deduced on the link vari¬ables, the propagation is finished.
Completeness of deduction is ensured with state propagation, whenever the colligation graph is acyclic. Thus, state propagation can be used on the follovvang structures:
• The configuration space of interconnected dusters on common link variables
• Object functions connected with the configuration space on common link variables
• Dynamic systems with predefined input and output variables (acyclic digraph)



20

7 Illustrative Examples
The following small examples illustrate different applications of the invention.
7.1 Combinational Network
The constraints of the small combinational network shown in Rg. 17 are given by the inter¬connections of the logical gates. The input file for the array database describes the domain of variables and the user-defined relations:



25

DOMAIN A, B, C,

Interim, Boolean; Int-eria, Boclean; Inreriin, BcolearL;

3^

10
15
20
25


D, Inrerim, DUUX^u^^ ,
E, Interim, Boolean;
F, Interim, Boolean;
G, Interim, Boolean;
H, Interim, Boolean;
Ir Interim, Boolean;
J, Interim, Boolean;
11, Input, Boolean;
12, Input, Boolean;
01, Output, Boolean;
02, Output, Boolean;
RELATIONS
A = not 11;
B = (11 and 12);
C = net 12;
D = not (A or
E = (D or 5);
F = (3 cr G);
G = not (B or C) ;
H = not D;
I = (E or F) ;
J = not G;
01 = = !H and I) r
02 = = {1 and J) r

Modeling the array database yields the following result with ail user-defined relations joined into a single database relation with just 4 legal states or combLnations:

A 0 1 1 1 0 0 0 1 J rL 12 Ol 02
0







1 1 0 0 1
0 1 0 0 1 1 0 1 1 1 1 1 1 1
1 0 0 1 0 0 1 1 1 1 0 0 1- 1 0
1 0 1 1 0 0 0 0 1 0 1 0 0 0 0

30

Table 35

We conclude that I1=02 and I2=01; that is, ail gates could be remQvedl
Z2

iU i3 .Jt=^rw*=,«..
I I -w V Ol iai^|\^ \m^ im.
In Fig. 18 an example or a simuiauon envKunmen serted/assigned the state 02=1 (true) with all consequences deduced. !t is seen that any variable or combination of variables can be used as input - there is no distinction between input and output variables.

7.2 Alarm System
Given the following input file for a small alarm system with three state variables on different data types:
10 DOMAIN
ALARM, Boolean;
SIGNAL, Enum(Red, Yellow, Green, Blue);
TEMP, Interval(]11;30], [100; [);
15 RELATIONS
TEMPI [100;[) -> SIGNAL(Yellow,Blue) ; TEMP (] 12 0; [) -> AiAJlM;
The t(W0 relations have one common variable TEMP and must therefore be colligated. Join-20 ing the relations yields the following array database with three legal Cartesian subspaces on a single relation:

AIAHM siramL: , - TKMP-
0,1 Red, Yellow, Green, Blue \ ]11;30]
0 Yellow, Blue 1 {10.0; 120]
1 Yellow, Blue ! [100; [
Table 36
Note that the relation is depicted with the legal domain vaiues rather than the domain/nd/ces. 25 The interna! binary representation is shown in Table 37.
a^

RLRSM.. SXGNjm.

TEMP



0.1

0,1,2,3

. 1 ^ u



1,3

1 ijlOO 120j
I ! !


1,3

Table 37
7.3 Product Configuration
We will now assume that a car manufacturer wants all the pcssfcie combinations of customer 5 options to be available on the Internet.
Given the following array database input file with the logical constraints of the cars:

10
15

DOMAIN Model,

Input, Enum(c3G0 "CAR 300",
c300i_cab "CAR 300 Cabriolet", c300_cab "CAR 300 Turbo 15 Ca; c3000_cc "CAR 3000 CC. c3000_cs "CAR 3000 CS", c3000_cd "CAR 3000 CD") , "Car model";



Engine, Input, Enum(ra_20_16
m_21_16
20 ra_s
ni_turbo_l 6
c_3000
c 3000 23

"2,01 16, 129 hp, 173 Nm / 3000 rpm", "2,li 16, 140 hp, 180. Nm / 2900 rpm", "2, OS 16, 145 hp, 205 Nir. / 3800 rpm", "Turbo 16, 160 hp, 255 Nm / 2800 rpm", "2,0 16, 130 hp, 173 Nm / 3750 rpm", "2,3 16, 150 hp, 212 Nm / 3800 rpm".

c_3000_2 3_turbo"2,3 Turbo, 200 hp, 330 Nm / 2000 rpm",
3S

c 3000_23_turbos 2,3 Tu^-— --
rpm" )
"Engine type";
-^^„> --^t=ae^(2 "Two doors", 5 Doors, ir.puu, ...^-g—v-
3 "Three doors",
4 "Four doors",
5 "Five doors") "Number of doors";
PaintT-.^e, Input, Enu:.(Normal "Normal paint",
Metallic "Metallic paint ) "The type of paint";
15 PaintColour, Input, Integer(153 "Cirrus white",
170 "Black",
198 "Embassy blue",
214 "Cherry red",
219 "Talladega rec",
223 "Odoardo grey meti /
20 . _ _ 1 T - r- "
22"7 "Citrin beige Tne_=.— -- -
228 "Platana grey ir.eta-iic ,
229 "Le Mans blue metallic",
230 "Scarabe green metallic",
231 "Monte Carlo yellow",
25
30
232 "Derby grey ,
233 "Carrara white",
234 "Nocturnal blue nietaliic ,
235 "Eucalyptus green metallic") "The paint colour";

35
40

WheelType, Input, Enum(NoAlloy "No Alloy wheels"^,
Alloyl "Alloy wheels -= spokes, open , Alloy4 "Alloy wheels, Aero design", Alloye "Alloy wheels, 15 spokes, closed", Alloy7 "Alloy wheels, 3 spokes, asymmetri , "Wheel type";
,1 . -^-;n ■^ r-,"im(MAS "Manually aQiustcDi- i-"-"i"
FroRtSeat, input, ::.a"im(nKi ^„,^"
EASl "Elec. adjust, left front seat ,
EAS2 "Elec. adjust, front seats",
3^

EAS2M "Elec. adjust, fror.t sears, rosmory ; , "Front seats tv-pe";
SunshineRoof, Input, £nuin(NoSSR "NoSSR",
SSRl "SSRl", SSR2 "SSR2", SSR3 ""SSR3") , "Sunshine roof";
10
GesrBox, Input, Enum(Manual "Manual",
Automatic "Automatic") , "Gearbox type";
15 RELATIONS
Model{c300i_cab) -> Engine(m_21_16);
Engine(c_3000) -> Model(c3000_cc,c3000_cs,c3000_cd); Model(c3000_cc) -> Engine(c_30Q0);
Model (c3000_cd, c3 000_cs) -> not Engine (m_2C_l€ , n:_i:i_l£, ni_s ,m_turbo_l5) 20 Model (c3D0_ca±;) -> Engine (m_turbo_16) ;
Engine(c_300G_23_turbos) -> Model(c3000_cs);
Engine(c_3000_23,c_3000_23_turbo) -> Model(c300C_rs,c30C0_cd); Model(c300) -> Engine{m_20_l6,m_21_1S,m_s,in_turbo_15); Model(c300i_cab,c300_cab) = Doors(2); 25 (Model(c300) and Engine (in_turbo_16) ) -> not Door3(4); Model(c3000_cd) -> Doors(4); Model (c3000_cs, c3000_cc) -> Doors (5);, Engine(m_20_l6) -> FrontSeat (MAS);
Engine{m_21_15,m_s,m_turbo_16) -> not FrontSeat[EASIM,EAS2M); 30 Engine(c_3000_23_turbos) -> FrontSeat(EAS2M); Model(c300_cab) -> FrontSeat(EAS2);
Model(c300i_cab,c300_cab) -> not FrontSeat(EASIK,EAS2M); (Model(c300) or Engine(m_21_16)) -> not FrontSeat(EASl,EAS2); Engine (in_20_16) -> not SunshineRoof (SSR3, SSR2) ; 35 Engine(m_21_l6) -> not SunshineRoof(SSR2);
Engine(c_30C0_23,c_3000_23_turbc,c_3000_23_turbos) -> not SunshineRoof(SSRl);
Engine(m_s) -> not SunshineRoof(SSR3); Engine (3i_turbc_l5) -> not SunshineRoof (SSRl, SSR.3) ; 40 Model(c3CC0_cc; -> SunshineRoof(NoSSR,SSR2);
Model{c300i cab,c3C0 cab) -> SunshineRoof(NoSSR);
2>1

(£ncin£(c -U"J"J) ana Moa-ei ICJ"JUU ua,i_juuu u.^ ; ; --■ .^ ;-
eRocf (SSP.l) ;
Model(c30C,c30Ci_cac,c3C0_cab) -> PaintColour ;2;3: ; Model(c500) -> net PainrColour(231,235); 5 cncine (c_3000, c_3000_23, c_3000_23_turbo, c_30:i0_23_-urocs i -> not ?aintCciour(231,235) ;
Engine (c_3000_23_ti:rbos) -> not PaintCol-ourd93,214,232, 233, 227, 230, 234) ;
Engine {>"n_20_16,m_21_16) -> not WheelType (Allcyl, Ali = y4 , Allcy7 ) ; 10 Engine(c_3000_23) -> not WheelType(Alloy4,Alloy6, Alloy" ) ; Engine(c_30C0_23_turbos) -> WheelType(Alloy4 ) ; Engine(c_3000_23_turbo) -> WheelType(Alloy!) ; Engine(in_s) -> WheelType (Alloyl) ;
Engine(m_turbo_l6) -> not WheelType(Alloy4,Alloy€!; 15 Model(c500_cab) -> WheelType(Alloy?);
(^odel (c300i_cab, c3000_cc) -> not WheelType (Alloyl, Alloy4 , Alloy7 ) ; (Engine(c_3000) and Model(c3000_cd,c3000_cs)) -> not WheelType(Alloyl,Alloy4,Alloy7);
(Modei(c300; and Engine (m_turbo_l 6) ) -> WheelTv-pe :Alloyi ) ,-20 Engine (c_3000_23_ti:rbos) -> GearBox (Manual) ;
PaintType(Metallic) = PaintColour(223, 227,22c,22 =,23 3,234,235);
Note that the user-defined relations can be written in any order and in many different ways. In the abovementioned relations, the user has written many symbolic expressions with logical 25 implications (IF-THEN) rather than a few tables. The modeling process is independent of the input format.
Modeling the input file yields the following array database with frve relations representing the configuration space of the car. These relations are interconnected by common link variables:
2^


^?

We claim
1. A method for generating a database for configuring and or optimizing a system
Spanned by variables on finite domains and/or intervals, the method comprising the
steps of:
generating and storing, in a memory or storage medium of a computer, an addressable
configuration space of the entire system in terms of all legal Cartesian subspaces of
states or combinations satisfying the conjunction of substantially all system
constraints on all variables, with all intercoimected legal Cartesian subspaces being
addressable as legal combinations of indices of link variables, so as to establish a
database in which substantially all legal solutions in the system are stored as nested
arrays.
2. The method as claimed in claim 1, wherein all illegal states or combinations violating the system constraints are excluded from the relations.
3. The method as claimed in claim 2, wherein, if just a single relation of a system is found to have no legal combination or state, the entire system is considered to be in a state of contradiction or inconsistency and is excluded.
4. The method as claimed in claim 1 or 3, wherein the system constraints are determined by conjugating one or more relations, each relation representing the legal Cartesian sub-spaces of states or combinations on a given subset of variables.

5. The method according to any of the preceding claims, wherein all relations with at least one common variable are colligated.
6. The method as claimed in claim 5, wherein the colligation comprises conjugating the constraints of two or more relations being connected by having common variables to establish the Cartesian subspace(s) satisfying the combined constraints of the two or more relations.
7. The method as claimed in claim 5 or 6, wherein the colligation of the two or more relations is performed by joining the two or more relations up to a predetermined limit, the resulting number of relations being colligated by linking them and grouping them into one or more cluster(s) of relation(s).
8. The method as claimed in claim 7, wherein each relation is extended by adding a unique link variable with a unique index identifying each legal Cartesian subspace on the given subset of variables.
9. The method as claimed in claim 7, wherein all connected relations are grouped into one or more clusters, each relation being associated with a single cluster of relation(s).

10. The method as claimed in claim 7 or 9, wherein three or more relations intercormected with common variables generating cycles or closed paths are grouped into a single cluster comprising the three or more relations, the resulting cluster(s) being interconnected in a tree structure without cycles.
11. The method as claimed in claim 10, wherein all constraints of the interconnected relations within each cluster are determined by colligating all interconnecting variables within the cluster thereby determining the configuration space of the entire cluster, all constraints between the three or more link variables being represented as one or more new relations on the three or more link variables.
12. The method as claimed in claim 9, 10 or 11, wherein any pair of relations with common variables linking two clusters is colligated by adding a new relation on the common variables and the two link variables.
13. The method according to any of the preceding claims, wherein an object function of a given subset of variables, the object function deriving characteristics of the given subset of variables, is linked to the complete configuration space by deducing the constraints on each link variable connected to the given subset of variables.

14. The method as claimed in claim 13, wherein the characteristics of the object function are determined and the constraints on the link variables are deduced on each combination of the given variables, the result being represented as a relation on the object function, the given variables, and the link variables.
15. A method for configuring and/or optimizing a system spanned by variables on finite domains, said method comprising the steps of
-providing a database generated by the method according to any of the claims 1-14
and
-deducing any subspace, corresponding to an input statement and/or inquiry, of states
or combinations spanned by one or more variables of the system represented by the
nested arrays by deriving the consequences of a statement and/or an inquiry by
applying the constraints defined by the statement and/or inquiry to the database.
16. The method as claimed in claim 15, wherein a deduction of any subspace of states or combinations is performed on a given subset of variable(s) colligated with or without asserted and/or measured states and/or constraints from the environment.
17. The method as claimed in claim 15 or 16, wherein all interaction between the systems represented by the array database and the environment is performed by a state vector (SV) representing all legal states or values of each variable.


18. The method as claimed in claim 16 or 17, wherein an input state vector (SVl) represents the asserted and/or measured states from the environment, while an output state vector (SV2) represents deduced consequence(s) on each variable of the entire system, when the constraints of SVl are colligated with all system constraints in the array database.
19. The method as claimed in claims 16 to 18, wherein the state of the entire system is deduced by consulting one or more relation(s) and/or one or more object function(s) at 30 a time by colligating the given subset of variables in the relation with the given subsets of states in the state vector and then deducing the possible states of each variable.
20. The method as claimed in claim 19, wherein two or more variables are colligated in parallel.
21. The method as claimed in claim 19, wherein the deduction of possible states is performed on two or more variables in parallel.
22. The method as claimed in claim 19, wherein completeness of deduction is performed by consulting connected relations until no consequences can be deduced on any link variable.
45

23. The method as claimed in claims 19-22, wherein at least two relations are consulted in parallel.
24. The method as claimed in claims 16-23, wherein a state of contradiction is identified by no legal states or values being deducible when consulting a relation.
25. A database for configuring and/or optimizing a system spanned by variables on finite domains and/or intervals, the database storing an addressable configuration space of the entire system in terms of all legal Cartesian subspaces of states or combinations satisfying the conjunction of substantially all system constraints on all variables, with all interconnected legal Cartesian subspaces being addressable as legal combinations of indices of link variables, so that substantially all legal combinations in the system are stored as nested arrays.
26. A database as claimed in claim 25 stored in a memory or storage medium of a machinery and/or computer and/or network.
27. A database as claimed in claim 26 which is stored in the memory or storage medium in such a way that it is accessible for deduction of any sub space of the system by applying input statements and/or inquiries to the database.
46


28. A database as claimed in claim 26 which is stored in a memory or storage medium which is adapted to be operably connected to a machinery and/or computer and/or network so that the database can thereby become accessible for deduction of any subspace of the system by applying input statements and/or inquiries to the database.
29. A machinery and/or computer and/or network comprising a memory or storage medium in which a database according to claim is stored.
30. A machinery and/or computer and/or network as claimed in claim 29 in which the database is stored in the memory or storage medium in such a way that it is accessible for deduction of any subspace of the system by applying input statements and/or inquiries to the database.
31. A network as claimed in claim 30 in which the database is stored in the memory or storage medium of one or more computer(s) in such a way that the database is accessible for deduction of any subspace of the system by applying input statements and/or inquiries to the database from any computer connected to the network.
A memory or storage medium having program instructions for carrying out the steps of the method as claimed in any of claims 1 to

33. A memory or storage medium as claimed in claim 32, wherein the database is
stored in such a way that it is accessible for deduction of any sub space of the system
by applying a input statements and/or inquiries to the database.
34. A memory or storage medium as claimed in claim 33 which is adapted to be
operably connected to a machinery and/or computer and/or network so that the
database can thereby become accessible for deduction of any subspace of the system
by applying input statements and/or inquiries to the database.

Documents:

in-pct-2000-0507-che abstract.jpg

in-pct-2000-0507-che abstract.pdf

in-pct-2000-0507-che claims-duplicate.pdf

in-pct-2000-0507-che claims.pdf

in-pct-2000-0507-che correspondence-others.pdf

in-pct-2000-0507-che correspondence-po.pdf

in-pct-2000-0507-che description(complete)-duplicate.pdf

in-pct-2000-0507-che description(complete).pdf

in-pct-2000-0507-che drawings-duplciate.pdf

in-pct-2000-0507-che drawings.pdf

in-pct-2000-0507-che form-1.pdf

in-pct-2000-0507-che form-13.pdf

in-pct-2000-0507-che form-19.pdf

in-pct-2000-0507-che form-26.pdf

in-pct-2000-0507-che form-3.pdf

in-pct-2000-0507-che form-5.pdf

in-pct-2000-0507-che others-document.pdf

in-pct-2000-0507-che others.pdf

in-pct-2000-0507-che pct.pdf


Patent Number 215938
Indian Patent Application Number IN/PCT/2000/507/CHE
PG Journal Number 13/2008
Publication Date 31-Mar-2008
Grant Date 05-Mar-2008
Date of Filing 11-Oct-2000
Name of Patentee ARRAY TECHNOLOGY APS
Applicant Address c/o Kobenhavns Forskerby Symbion, Fruebjergvej 3, DK-2100 Copenhagen,
Inventors:
# Inventor's Name Inventor's Address
1 MOLLER, Gert, Lykke, Sorensen Dianas Have 73, DK-2970 Horsholm,
2 JENSEN, Claus, Erik Ornebjergvej 3E, DK-2600 Glostrup,
PCT International Classification Number G06F 17/50
PCT International Application Number PCT/DK1999/000132
PCT International Filing date 1999-03-16
PCT Conventions:
# PCT Application Number Date of Convention Priority Country
1 0363/98 1998-03-16 Denmark