From: mcgregor@netcom.com (Scott Mcgregor)
Subject: Re: Patents:  What they are.  What they aren't.  Other factors.
Organization: Netcom - Online Communication Services (408 241-9760 guest)
Distribution: usa
Date: Tue, 6 Oct 1992 01:13:44 GMT

In article <DGAY.92Oct3130119@disun46.epfl.ch> dgay@di.epfl.ch (David Gay) writes:
>In article <1992Oct1.231728.8419@netcom.com> mcgregor@netcom.com (Scott Mcgregor) writes:
>   In article <RLK.92Oct1161235@underprize.think.com> rlk@underprize.think.com (Robert Krawitz) writes:

>   >the patent might be violated only by combinations of subroutines.
>
>   This just argues that the total number of patents is even smaller than
>   I was allowing. 
>
>A well known mathematical theorem (due to Georg Cantor) says that the
>power set of S always has a greater cardinality than that of S. I'm
>impressed that you have found a counter-example (and a very good one
>at that, the cardinality of the power set is actually lower.  Really
>impressive).

I don't catch Gay's point. My point is about granularities.
Another way of looking at this is that the smaller the
granularity that might reasonably be patented the more patents there
could be lurking in a given program.  If the granularity is lines on
average, then the cardinarlity  is going to be a larger than if it the
granularity is subroutines.  Subroutines in turn have a larger
cardinality than larger algoritmns consisting of a combination of
algorithms. The smallest cardinality is if patentable pieces are at
the level of application program. Then there is only one possible
patent. Then number of patents that you could be inadvertantly
infringing goes down as the average size of a patentable object goes
up. The probability of being sued for infringement goes down as the
number of possible infringements declines.  How Gay read a
counter-example to the power set theorem in this I don't know, but it
wasn't the intent of my passage, and I don't think that is is relevant
at all to what I was intending.
 
>   True, but most COTTAGE INDUSTRIES have a great many more DESIGN
>   patents than software does. The ability to tell if one design is the
>   same is even more of a judgement than is telling two algorithms. At
>   least in the algorithm case you can run a putative test case. 
>
>I'm curious. It would seem that you feel that two algorithms are
>identical if they wield identical results for identical inputs (this
>is presumably what your test case is for). This means that I can
>patent the bubble sort (or more likely, invent some new and preferably
>inefficient sorting method), patent it, and then sue every program
>which sorts any data. This should make me seriously rich.

Mr. Gay's suggestion seems a naive read on the patent system.  The
important thing is the patent claim.  If Mr. Gay is granted a patent
with a claim that reads "a method  which given an unsorted list of
information, encoded into a set of binary electrical patterns, which
when acted upon by a central programming unit running a software
program generates an output set of patterns which may be decoded into
a sorted list of that information..." then Mr. Gay would seem to be
right. 

But due to prior art, the PTO is not likely to grant such a broad claim, 
and Mr. Gay will probably be forced to narrow it.  Furthermore, even if
granted, and if Mr. Gay were to sue for example, Mr. Knuth (a well known and
blatent user of bubble sort), then Mr. Knuth might well defend by
demonstrating prior art (showing that bubble sort and quick sort had
been published before Mr. Gay's application).  At that point, the
courts would likely strike down Mr. Gay's patent or narrow its scope.
Conceivably by replacint "a software program" above with "a software
program firs does (step A) and then (step b)" etc. until it only
covers the inefficient method Mr. Gay invented (how the "inefficient"
algorithm also passed the usefulness requirement isn't clear to me).
Since Mr. Gay's patent attourney is no slouch, and Mr. Gay doesn't
want to waste money on suits he can't win, Mr. Gay would actually not
sue Mr. Knuth and Mr. Knuth would not be inconvenienced. Thus
unhappily Mr. Gay would not become as rich as he thought--this is
frequently the case when we impute easy riches to be had in an area
outside of our expertise.

>Of course, maybe you didn't mean that ? This of courses raises the good
>question of when two algorithms can be considered identical.

What I did intend was that a way to disprove infringement is to  take
an input specified in the claim, the two software programs and the
claimed result. If the allegedly infringing program does not generate
the same result as the claimed program (i.e. the claimed benefit) it
is evidence that it is not infringing.  

But, yes two programs are identical from a patent perspective  if they
take the same  inputs and produce the same outputs, using the same
equipment if there are no other specifics in the claims. To the extent
that the claims mention specific steps, the programs must also both
follow those steps in the correct order, but programs are free to  be
different with respect to things not in the claims (C vs. Fortran,
etc.).  Note that this describes how "processes" involving programs
are identical from a patent infringement perspective. This isn't the
same thing as proving two algorithms identical mathematically, because
patents cover processes not algorithms, and identical with respect to
patent claims is not the same as mathematically equivalent.  It is
more like in object oriented programs, two objects with the same
public interfaces may be equivalent even though they differ in private
methods.
-- 

Scott L. McGregor		mcgregor@netcom.com
President			tel: 408-985-1824
Prescient Software, Inc.	fax: 408-985-1936
3494 Yuba Avenue
San Jose, CA 95117