RE: Comments on decoration ill, intersection and union
Vincent Lefevre wrote:
> From: stds-1788@xxxxxxxx [mailto:stds-1788@xxxxxxxx] On Behalf Of Vincent
Lefevre
> Sent: Tuesday, December 04, 2012 9:48 AM
> To: 'stds-1788'
> Subject: Re: Comments on decoration ill, intersection and union
>
> On 2012-12-03 11:15:32 -0600, Nathan T. Hayes wrote:
> > Using the min rule to perform a lengthy computation returns a decoration
> > EIN, DAC, DEF, TRV or EMP with the following meaning (I use UPPERCASE to
> > distinguish a decoration computed by lengthy computation/propagation as
> > opposed to lowercase to distinguish the mathematically true decoration
of
> > any (f,xx) pair):
> >
> > Result The mathematically true decoration of (f,xx) is:
> > EIN => ein
> > DAC => ein or dac
> > DEF => ein or dac or def
> > TRV => ein or dac or def or emp
> > EMP => ein or emp
...
> > > > This allows set-theoretic operations like intersection and union to
be
> > > > decorated. For example, the function in Example 2 on pp. 34-35 may
be
> > > > implemented:
> > > > U = f1(X intersect [-oo,-2])
> > > > V = f2(X intersect [-2,2])
> > > > W = f1(X intersect [2,+oo])
> > > > return U union V union W
> > >
> > > X is the input. If it is not empty, you'll never get ein in the
> > > propagations, unless you have special rules for ein.
> >
> > If X is Empty, the result is (Empty,DAC), since, for example:
> > U = f1((Empty,ein) intersect ([-oo,-2],dac))
> > = f1((Empty,DAC))
> > = (Empty,DAC)
>
> But what if only the intersection is empty, say if X = [0,1]?
>
> ([0,1],dac) intersect ([-oo,-2],dac) = (Empty,DAC)
>
> though the input X is *not* empty. So, DAC is meaningless:
> * The true decoration cannot be ein because the input is not empty.
> * The true decoration cannot be dac because a dac function over a
> non-empty interval cannot have an empty result.
Consider the function g(x) = x and intervals X=[0,1], Y=[2,3].
If we take the intersection of the ranges of g(X) and g(Y), then
g([0,1]) intersect g([2,3])
= g(([0,1],DAC)) intersect g(([2,3],DAC))
= ([0,1],DAC) intersect ([2,3],DAC)
= (Empty,DAC)
If we evaluate the range of the intersection of X and Y, then
g([0,1] intersect [2,3])
= g(([0,1],DAC) intersect ([2,3],DAC))
= g((Empty,DAC)) // Empty input!!!
= (Empty,DAC)
So in this decoration system, the operation
([0,1],dac) intersect ([-oo,-2],dac) = (Empty,DAC)
doesn't pose any contradiction. The (Empty,DAC) result can be viewed as a
containment of the empty input that occurs in the equivalent formulation
where the range of the intersected domains is instead computed.
Back to Example 2, for example, gives:
U = f1([0,1] intersect [-oo,-2]) = f1((Empty,DAC)) = (Empty,DAC)
V = f2([0,1] intersect [-2,2]) = f2(([0,1],DAC)) = (f2([0,1]),DAC)
W = f1([0,1] intersect [2,+oo]) = f1((Empty,DAC)) = (Empty,DAC)
and the union of U, V and W is a nonempty interval with DAC decoration,
which I believe everyone expects should be the correct result.
Nate