Anders Johansson wrote:

What I really wish though, is that the US legal system changed, so that the losing party in such a law suit had to pay legal costs for the winner.

This would tilt the system to favor wealthy corporations even more than it already does. Already, an individual is at a great disadvantage when suing a corporation, because the corporation can bring more money and legal expertise to bear. If the individual faced having to pay the corporation's legal fees as well as their own, a lot of cases would never get filed, even if the individual was likely to win, because the risk would be too high. -- To unsubscribe, e-mail: opensuse+unsubscribe@opensuse.org For additional commands, e-mail: opensuse+help@opensuse.org

On Mon, 19 Mar 2007 20:37:58 -0000 (GMT) (Ted Harding) wrote:

For example, does it occur in standard textboooks on computer programming and data structures? Is there long-standing open source software in which it may be found?

Well, it is essentially the way all relational databases work, so they should clearly sue Oracle for a million billion zillion dollars. -- To unsubscribe, e-mail: opensuse+unsubscribe@opensuse.org For additional commands, e-mail: opensuse+help@opensuse.org

On 19-Mar-07 21:00:37, Tom Horsley wrote:

On Mon, 19 Mar 2007 20:37:58 -0000 (GMT) (Ted Harding) wrote:

...

For example, does it occur in standard textboooks on computer programming and data structures? Is there long-standing open source software in which it may be found?

Well, it is essentially the way all relational databases work, so they should clearly sue Oracle for a million billion zillion dollars.

Can you expand and clarify that? I can see that storage in a relational databse table (i.e. "relation") is facilitated by using a "double-linked list" (in the *traditional* sense I described at [1] in my previous mail), where each record is associated with two pointers, one to its successor in some desired order (e.g. alphabetical sort) and the other to its predecessor. But is the *other* "double-linked list" as I described at [2] of my previous mail generally used -- i.e. is each record associated with two or more sets of pointers, where, in one set, one pointer points to the successor in one ordering and the other pointer to its predecessor in the same ordering; and in another set one pointer points to the successor in a different ordering and the other points to its predecessor in this different ordering, and so on? You say "it is essentially the way all relational databases work", which -- if we are talking about the same interpretation -- means that in all relational databases each record in a relation is associated with multiple forward pointers and a matched set of multiple backward pointers. Is that the case (speaking from ignorance here)? It is the second interpretation of "double linked list" which is the subject of the patent, not the first! With thanks, Ted. -------------------------------------------------------------------- E-Mail: (Ted Harding) Fax-to-email: +44 (0)870 094 0861 Date: 19-Mar-07 Time: 22:12:46 ------------------------------ XFMail ------------------------------ -- To unsubscribe, e-mail: opensuse+unsubscribe@opensuse.org For additional commands, e-mail: opensuse+help@opensuse.org

On 19-Mar-07 21:29:52, Anders Johansson wrote:

On Monday 19 March 2007 21:37, Ted Harding wrote:

...

Now, while the standard "doubl{e|y} linked list described at [1] above has been around since the year dot (or shortly thereafter), and is found everywhere, the second kind described at [2] above (though it has undoubtedly been implemented many times) could conceivably be considered sufficiently novel to provoke a patent application!

It certainly fails the "obvious to one skilled in the field" test

...

So my question, for clarification, is: Can anyone supply any reference of sufficiently long standing to demonstrate that the second kind of "double linked list" at [2] above is well established prior art?

They are sorting the list in various ways, and storing the previous results so they don't have to do them all over again when they need them again. If

struct foo *next, *prev

is old hat, why would

struct foo *next[100], *prev[100]

be a patentable invention.

They are storing various paths in traversing a tree or graph. There is absolutely nothing about that that isn't patently (if you'll pardon the pun) "obvious to one skilled in the field"

I absolutely agree that it's an obvious generalisation, and I'm pretty sure that it's been used many times. But the "trick" when making a claim for novelty is to isolate, abstract and identify the concept as adapted to a class of purposes, and give it a name. So what I was after is whether there exists such an identification of this technique that has been around long enough to well-established prior art. That has certainly been the case for struct foo *next *prev (see good books on C programming from 20 years ago) but what about the other? And, just to make it clear, I oppose the whole concept of patentability of programming techniques, since in principle -- given the abstract definition of any given programming language -- all constructs stateable in the laguage are implicit in its definition; and therefore to anyone "skilled in the field" they should be available as an inspirational mental perception that "this is how to solve this problem". To inhibit this by patent is to inhibit thought itself. On the other hand, I think the concept of copyright in a publication of a programming technique can be defended. What is then prohibited is the unauthorised deliberate copying from the publication. But then what has to be proved is the act of copying, not the fact that it is the same technique. The same technique could arise by mental inspiration, but then while the program's structures could be identifiably the same, the precise details would differ (perhaps in order and detail of definitions, or variable names, etc.). However, if the copier's code were character-by-character identical to the original, then this would justifiably be viewed is totally improbable as an independent creation. Thanks Anders! Ted. -------------------------------------------------------------------- E-Mail: (Ted Harding) Fax-to-email: +44 (0)870 094 0861 Date: 19-Mar-07 Time: 22:37:32 ------------------------------ XFMail ------------------------------ -- To unsubscribe, e-mail: opensuse+unsubscribe@opensuse.org For additional commands, e-mail: opensuse+help@opensuse.org

On Monday 19 March 2007, Ted Harding wrote:

So what I was after is whether there exists such an identification of this technique that has been around long enough to well-established prior art.

Since when is the test "well established prior art"? Any prior art should suffice. We used similar structures years ago in maintaining computerized specification of sequences of laboratory procedures defining a medical lab "test" (such as a tests for strep throat or rabies, etc) for a certain State Medical Lab. The same basic steps are used in many different test, and we simply carried multiple doubly linked lists to the sequence of steps. When viewed from the point of view of a individual step, you might find dozens if not hundreds of such linked lists specifying each place in the sequence this step appeared. This is a basic building block of any relational database. -- _____________________________________ John Andersen

On Monday 19 March 2007 13:37, Ted Harding wrote:

...

So my question, for clarification, is: Can anyone supply any reference of sufficiently long standing to demonstrate that the second kind of "double linked list" at [2] above is well established prior art?

You might want to read about "Skip Lists." They're a way of an ordered collection starting with a conventional linked list augmented by layers of extra links. Each successively layer skips further per link. It's kind of like an ordered tree with each depth of the tree represented by a separate linked list. That's poor explanation, but it is vaguely like the data structure described earlier in this thread and illustrates an openly published data structure that is significantly more subtle and less obvious than the one here.

For example, does it occur in standard textboooks on computer programming and data structures? Is there long-standing open source software in which it may be found?

Skip lists appear extensively in the computing literature, but are a relatively new invention by comparison to other basic linked structures. They are credited originally to Willilam Pugh in 1990. (See ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf). It has since spawned follow-on research to elaborate or modify the basic structure (e.g., to allow for fast concurrent access and update). I've implemented Skip Lists as an experiment to find a fast and stable priority queue. They can be made stably sorted, but do not appear to be faster than a heap-based priority queue (which is not stably ordered).

Thanks! Ted.

Randall Schulz -- To unsubscribe, e-mail: opensuse+unsubscribe@opensuse.org For additional commands, e-mail: opensuse+help@opensuse.org

On Tuesday 20 March 2007 04:52, Matthias Hopf wrote:

On Mar 19, 07 15:36:43 -0700, Randall R Schulz wrote: ...

What exactly do you refer to as a priority queue? Queues can be implemented in a number of different ways...

A priority queue is one in which the items bear priority values (usually numeric, but requiring only a total ordering). When removing items from a priority queue the entry with the smallest (or largest) priority value is the one removed. Items may be inserted with priority values in an arbitrary order. Usually insertion is interleaved with removal. Common uses are time-based / event simulation (where time is the priority value) or heuristic search (in which case heuristic figures of merit constitute the priority value). The classic means of implementing a Priority Queue is with a binary heap, and it is very efficient. It does not, however, maintain the insertion order of entries with equal priority values.

Matthias

Randall Schulz -- To unsubscribe, e-mail: opensuse+unsubscribe@opensuse.org For additional commands, e-mail: opensuse+help@opensuse.org