[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:


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 mailing list