[Foundation-l] [offtopic] Lempel-Ziv Was: Freedom, standards, and file formats

[Gregory Maxwell]

On Tue, Sep 30, 2008 at 8:55 PM, Jussi-Ville Heiskanen
<cimonavaro at gmail.com> wrote:
> I am aware that I am dating myself there.
>
> As I recall it, (and my recollection is as ever fallible)
> there was a claim by some that a compression format
> was protected. And it was upheld. But the mathematical
> algorithm wasn't protected, so a totally equivalent
> format was created (and if I recall improved upon) later,
> and the original claimants for protection got their butts
> spanked, even though their claim held.

http://en.wikipedia.org/wiki/Compress

LZW was patented. It was replaced, but not by a mathmatically
equivalent alternative, but instead by a superior non-identical
alternative. This is why .tar.gz files are common today, but tar.Z
files are usually not found.

(Likewise gif -> png, but the story was a bit different since it
wasn't realized that GIF had patent problems until very late, and it
was possible to make non-infringing GIFs by not applying the
compression)

It's true that math is not itself patentable in the US.  The way
software patents are constructed is by saying: "We claim a computer
system (a) consisting of transistors and all the usual computer
trappings, which is loaded with software (b), which tranforms the
computer into a device for performing computation (c; described in
great detail), so that the resulting system a+b+c, is useful for
performing task X", and that *is* patentable in the US,  the patents
usually go on to describe every application that they can think of, as
well as the most obvious permutations of a,b, and c.

This does have the effect of source code itself not infringing, but
that the infringement begins as soon as the source is combined with a
computer that can run it.  The distinction is interesting to pedants
and lawyers,  but the end result is nearly the same as if the
algorithm were patented.

There are some cases where someone patents a system using algorithm X
and it's possible to find some isomorphic Y which does different
computation but gets the same result without infringing on the patent,
but LZW was not one of those cases.  I get the impression that such
examples are fairly uncommon.