Information Technology Reference
In-Depth Information
Definition 3. (Combination function). Let φ ( u, v ) be a term in which u and v
occur only once. The underlying combination function ϕ is defined as follows:
2
T
T
ϕ :
( f, g )
φ [ u
f, v
g ]
In the following every function ϕ will be supposed to be associated with a term
φ ,evenif φ is not mentioned. These functions are used to process projection
constraints of the form f
I . The combination method is described in the
following lemma, the result being a redundant constraint.
Lemma 2. Let f and g be two terms and let I and J be two intervals. Given a
combination function ϕ , the following relation holds:
f
I
g
J =
ϕ ( f, g )
φ I ( I,J )
The previous lemma is interesting since it shows how to introduce a redundant
constraint. Terms f and g are combined by ϕ and the evaluation of φ I on ( I,J )
gives a range of the redundant term ϕ ( f, g ). However, the following lemma shows
that this redundancy is useless for box consistency computations.
Lemma 3. Let D be a box and let ϕ be a combination function. Let C : f
I
and C : g
J be two projection constraints such that f I ( D ) is box consistent
wrt. C and g I ( D ) is box consistent wrt. C .If C is the redundant constraint
defined by ϕ ( f, g )
φ I ( I,J ) then f I ( D ) and g I ( D ) are box consistent wrt. C .
The previous lemma shows that the redundant constraint does not allow to
reduce the domain of f since it is already box consistent. As a consequence, the
redundancy is useless. The next step introduces a simplification process.
3.3
Term Simplification
Simplification procedures are generally associated with two properties. Firstly,
the equivalence of terms in the domain
must be preserved. Secondly, rewritten
terms have to be adapted for further computations. The first property is the basis
of the following definition.
R
Definition 4. (Simplification function). A simplification function ψ is a func-
tion on terms such that for all f ( x 1 ,...,x n )
T
, the set of variables occurring
in ψ ( f ) is included in
{
x 1 ,...,x n }
and the following formula is true in the real
structure:
x n f = ψ ( f )
The main idea is to simplify left-hand terms of redundant projection constraints.
The following lemma shows that the redundancy property (Lemma 2) is pre-
served by simplification.
Lemma 4. Let f
x 1 ...
J be two projection constraints. Given a combi-
nation function ϕ and a simplification function ψ , the following relation holds:
I and g
f
I
g
J =
ψ ( ϕ ( f, g ))
φ I ( I,J )
Search WWH ::




Custom Search