RE: Comments on decoration ill, intersection and union

["Nathan T. Hayes" <nh@xxxxxxxxxxxxxxxxx>]

Vincent Lefevere wrote:
> On 2012-12-01 11:19:27 -0600, Nathan T. Hayes wrote:
> > John, P1788,
> >
> > It appears that knowing Dom(f) is empty requires global knowledge of the
> > function f. For example, some Computer Algebra System (CAS) or a user's
> > comprehensive run-time knowledge of an entire program may be required.
But
> > complicated functions may be composed from collections of smaller
functions
> > or subroutines that are part of pre-compiled libraries, for instance, so
> > even a CAS may not be able to prove the ill decoration. This leads me to
> > think it should be dropped.
> 
> AFAIK, ill was introduced mostly for an "illegal" use of a constructor,
> e.g. nums2interval(1,0) in the set-based flavor, then extended to the
> cases when an implementation could deduce that a function is nowhere
> defined (the implementation needs to be smart enough, because supplied
> arithmetic operations are never nowhere defined in practice, only some
> special composition can), and to incorrect constants like 1/0.
> 
> An implementation is not required to return the best decoration, as
> said in §8.8.4. Also note that from the definition, ill implied emp
> (if Dom(f) is empty, then xx inter Dom(f) is also empty), so that
> there is no contradiction.

I understand.


> 
> > On a different topic:
> >
> > Empty is a subset of any interval in set-theory. I think it is
advantageous
> > to have a decoration that has this property too, i.e., a decoration that
is
> > a "subset" of every other decoration. This would be the decoration ein
for
> > "empty input" with property p_ein(f,X) defined as X is empty, and the
> > restriction of f to X is (vacuously) continuous.
> >
> > Removing ill and adding ein would give the propagation order:
> > 	ein > dac > def > trv > emp
> > and the exclusivity rule is satisfied such that ein is a subset of every
> > decoration.
> 
> There were consistency problems with ein when it was introduced in
> the past.

Indeed. Motion 26 did not incorporate ein properly and had contradictions,
e.g., see section 6.2.3 in the attached paper that explains why. I was not
an author of Motion 26, and this was one of my reasons for voting "no" on
that motion.


> So, you need to be careful. For instance, the min-rule
> would no longer be valid. because ein could be transformed to dac,
> which is wrong, as dac assumes that xx is nonempty.

Decorations in the propagation order
	ein > dac > def > trv > emp
each define some contradictory (exclusive) property over all other
decorations, e.g., dac is the set of all (f,xx) pairs of nonempty xx such
that "the restriction of f to xx is defined and continuous," and def is the
set of all (f,xx) pairs such that "Dom(f) intersect xx is not empty and
(f,xx) is not an element of dac."

Similarly, if Sigma is the set of all (f,xx) pairs where the restriction of
f to xx is defined and continuous, then Sigma can be partitioned into
disjoint subsets such that ein is the subset of Sigma were xx is empty and
dac is the remaining portion of Sigma.

In this sense, def is the subset of all (f,xx) pairs such that "the
restriction of f to xx is defined and (f,xx) is not an element of Sigma."

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 forms the containment order:

	EIN \subseteq DAC \subseteq DEF \subseteq TRV \supseteq EMP
\supseteq EIN

such that EIN is a subset of every decoration.


> > 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)

By the containment order above, DAC is a superset of EIN. So no special
rules were required to compute this result. It is not the best decoration,
but by the containment order it is a correct decoration.

If the input is nonempty, the default rules produce some nonempty interval
with the DAC decoration, a result I think everyone expects.

Note that under the current proposal without EIN, if intersection and union
operations propagate decorations the result for any nonempty X would be a
nonempty interval with an EMP decoration. That would definitely be a wrong
result, and explains why intersection and union can't propagate decorations
using the proposed decoration system.

Nate

Attachment: hayesdsm.pdf
Description: Adobe PDF document