[Ecls-list] Re: HEADS UP!
Paul F. Dietz
dietz at dls.net
Wed Apr 9 15:44:06 UTC 2003
Juan Jose Garcia Ripoll wrote:
> The interesting thing about Baker's approach is that there is no scalability
> problem. Performing a SUBTYPEP takes O(2N^2) operations, where N is the
> number of elements in the type (and maybe pre-registered types).
Baker worked on his algorithm just before the CONS type specifier was
added. With (CONS ... ...) types, a type specifier of size N can
specify a type with exponentially many (in N) elements. For example:
(CONS BIT (CONS BIT (CONS ... (CONS BIT NULL) )))
With n BITs, this specifies all proper lists of length n whose elements
are 0 or 1.
It's not hard to reduce the tautology problem on disjunctive normal
form boolean formulas to a subtypep query on cons types. DNF tautology
is co-NP complete.
More information about the ecl-devel