Partial List Of Software Patents
maintained by Michael Ernst <mernst@theory.lcs.mit.edu>

You can ftp this file from mintaka.lcs.mit.edu:/mitlpf/ai/patent-list.
That site is mirrored by jupiter.ee.pitt.edu:pub/patent/patent-list and
possibly prep.ai.mit.edu:/pub/lpf/patent-list.
The original is rice-chex.ai.mit.edu:/home/fsf/rms/lpf/patent-list.
It was last updated on April 12, 1992.  (I often forget to update this line.)

This is a list of software patents for which the disclosure statements are
in this file folder (i.e., in NE43-427), plus information about all other
software patents that I know of.  It is a partial list.  If you know of
patents that I haven't included, or if you have more information about any
of these, I would appreciate hearing about it.  Except where otherwise
noted, the patents are US patents.

Its format is
 number
 title
 filing date
 granting date
 assignee or owner
 inventor
 notes

3,879,722
Interactive input-output computer terminal with automatic relabeling of
keyboard
On-screen image is projected onto keyboard, which can provide useful
information about what keys do what.

4,135,240
Protection of data file contents
filed 7/9/73
granted 7/16/79
inventor Dennis Ritchie
The set uid bit patent.
Doug McIlroy <doug@research.att.com> says:  "AT&T distributed Unix with the
understanding that a license fee would be collected if and when the setuid
patent issued.  When the event finally occurred, the logistical problems of
retroactively collecting small fees from hundreds of licensees did not seem
worth the effort, so the patent was placed in the public domain."

4,158,837
Information display apparatus
filed 5/17/77
granted 6/19/79
inventor James T. Zahorsky
assignee IBM
abstract:  "A display system is shown which has a source of coded
information in display mapped format and includes plural devices for
decoding and utilizing the information in accordance with its position in
that mapped format.  In the illustrated embodiment, the source includes a
refresh buffer and the utilization devices include an attribute decoder and
a character generator.  A character row counter controls gating which
causes the apparatus to treat bytes of data, having attribute format, truly
as attributes or as addresses of members of an extra, graphical character
set of the character generator."

4,197,590
Method for dynamically viewing image elements stored in a random access
memory array
filed 1/19/78
granted 4/8/80
inventors Josef S. Sukonick; Gred J. Tilden
assignee NuGraphics, Inc.
Includes claims of "XOR feature permits part of the drawing to be moved or
'dragged' into place without erasing other parts of the drawing."
Twice upheld in court.  [Cadtrak now owns this?]

4,398,249
Process and apparatus for converting a source program into an object program
filed Aug 12, 1970
granted Aug 9, 1983
inventors Rene' K. Pardo and Remy Landau
This is the natural order spreadsheet recalculation patent recently
acquired by Refac, a litigation company.  Draws on ideas like forward
reasoning.

4,410,958
Displaying a proportionally outlined miniature page
filed 12/24/80
granted 10/18/83
inventors Kent R. Demke, Joanne L. Mumola
assignee IBM
Abstract:  "There is disclosed a technique for displaying on a relatively
small CRT display, using less than the entire screen, a representation of a
full page of text.  The full page is represented using character indicators
rather than recognizable characters.  The full page representation is
surrounded by an outline generated using the same character indicators as
the formatted text representation rather than known graphic symbols.  The
outline is proportional to the ultimate hardcopy indicated by the user, and
character indicators can be displayed right up to the page outlines."
See also 4,455,554.
[Have only first page of this patent.]

4,449,182
Interface between a pair of processors, such as host and
peripheral-controlling processors in data processing systems
filed 10/5/81
granted 5,15,84
inventors Barry L. Rubinson, Edward A. Gardner, William A. Grace, Richard
F. Lary, and Dale R. Keck
assignee Digital Equipment Corporation
This patent apparently covers ring buffers.

4,455,554
Proportionality in miniature displays
filed 12/30/81
granted 6/19/84
inventor Kent R. Demke
assignee IBM
Display a full page of text on a CRT by representing every 8x16 character
by a character indicator (a 2x4 screen pixel blob); proportionality is
maintained (that is, the screen looks like a miniature of the actual
printed page) by inserting dummy characters in words with especially wide
letters (so "fox", which has no narrow letters might be represented by four
character indicators, but "quick" would be represented by five character
indicators).  See also 4,410,958.

4,458,311
Text processor having an interactive display terminal which alternately
functions as a data processing terminal
filed 10/9/81
granted 7/3/83
inventors Silous F. Clements, Patrick D. Motola, Dennis M. Ross, Richard O.
Simpson, Shirley F. Swift, Michael N. Day
assignee IBM
The user is permitted to modify the way that a database front end displays
information; a single terminal can be used both to enter or change data and
to change the way the data is displayed.

4,464,650
Apparatus and method for compressing data signals and restoring the
compressed data signals
inventors Lempel, Ziv, Cohn, Eastman
assignees Sperry Corporation and At&T Bell Laboratories
filed 8/10/81
granted 8/7/84
owner Sperry Corporation (now Unisys)
Invented 1976, published IEEE Trans Info Theory 1978.
This is one of the LZW patents.

4,514,818
Video image creation system which simulates a drafting tool
filed 12/1/81
granted 4/30/85

4,555,775
Dynamic generation and overlaying of graphic windows for multiple active
program storage areas
filed 10/7/82
granted 11/26/85
inventor Robert C. Pike
owner AT&T
Lawsuits of X window vendors threatened, since this covers backing store.
jupiter.ee.pitt.edu:/pub/patent/backing-store-letter is text of AT&T's letter.
AT&T says, "The `backing store' functionality available in the
X Windows System is an implementation of this patented
invention, therefore, your company/institution needs a license
from AT&T for the use of this patent."
The MIT AI Lab implemented this three years before the patent application
was filed, but the implementor (Richard Stallman) didn't think it was
worthwhile enough to publish a paper on.
janson@Athena.MIT.EDU says of Pike's _Transactions on Graphics_ articles on
backing store and on the Blit:
"a few things jumped out:
1) pike referenced prior art for naive backing store in the form of 
symbolics' window system
2) he distinguished his methods by virtue of special mechanisms to
store the minimal amount of data rather than the entire window contents,
and by specifying algorithms to perform graphics operations directly on
this specially structured (composite backing store / frame-buffer) `window'."

4,558,302
High speed data compression and decompression apparatus and method
filed 6/20/83
granted 12/10/85
assignee Sperry Corporation (now Unisys)
inventor Welch
Covers the common "compress" algorithm published in IEEE Computer, June 1984.
Also see Welch's article in CACM.
The text for patent "4,558,302 Dec. 10, 1985 Welch" can be ftped from
uunet.uu.net as pub/lzw-patent.Z
Independently discovered by Victor Miller and Mark Wegman (see 4,814,746,
which is identical and takes precedence because it was filed 19 days
earlier).
Adds one table initialization and two lines of change to 4,464,650.

4,586,158
Screen management system
filed 2/22/83
granted 4/29/86
inventor Richard T. Brandle
assignee IBM
Maybe covers termcap-style declarations of terminal characteristics.
abstract:  "A method of providing efficient on-line and interactive
application program utilization of an assortment of devices calling for
different screen characteristics.  An application programmer writes screen
definitions for a particular device to be used.  These definitions are
stored exterior of the application program and are used to define the
quantity, order, and placement of the application program's information on
the screen.  The application program provides services to generate and
process each data element which can be presented.  These services are used
by a mapping system in conjunction with the screen definitions to generate
and process a device dependent data stream."

4,602,286
Video processing for composite images
filed 1/10/83
granted 7/22/86

4,622,641
Geometric display generator
filed 9/13/83
granted 11/11/86
inventor Lawrence  K. Stephens
assignee IBM
Apparently covers all draw and paint programs
Abstract:  "A user-friendly procedure for the generation and display of
geometric figures on a graphics screen uses a cursor placement device such
as a joy stick to both define the initial position and size of the
geometrical figure.  Two specific examples are described:  the generation
of a circle and the generations of a square or rectangle.  In the first
example, the cursor is first positioned to point to the center of the
circle at which point a small circle is drawn.  The circle is expanded in
response to the pressing of a designated key by the user until the desired
size is attained.  In the second example, the pointing by the cursor is to
the upper left corner of the square or rectangle, and the square or
rectangle is then expanded in response to the user deflecting the joy stick
down and to the right."

4,627,015
Text placement on graphics screen
filed 5/31/83
granted 12/2/86
inventor Lawrence K. Stephens
assignee IBM
abstract:  "A personal computer having an interactive all points
addressable display terminal and a cursor positioning device is provided
with a keyboard for inputting alphanumeric character strings not exceeding
a predetermined maximum length.  Once the desired alphanumeric character
string has been input, it can be selected as the current cursor character.
As the selected current cursor character, the alphanumeric character string
is displayed on the all points addressable display and movable by said
cursor positioning device.  When the alphanumeric character string is
positioned at a desired location on the all points addressable display, it
can be fixed in that location by reading the alphanumeric character string
into the display buffer."

4,633,416
Video image creation system which simulates a drafting tool
filed 7/29/85
granted 12/30/86

4,642,764
Method of developing formal identities and program bases in an optimizing
compiler
filed 8/13/84
granted 2/10/87
IBM
Optimizing compiler patent

4,642,765
Optimization of range checking
filed 4/15/85
granted 2/10/87

4,646,250
Data Entry Screen
filed 10/18/84
granted 2/24/87
assignee IBM
inventor John F. Childress
Required fields are highlighted until they are filled in; fields
incorrectly completed are also highlighted.

4,648,062
Method for providing an on line help facility for interactive information
handling systems
filed 2/1/85
granted 3/3/87
inventors Steven E. Johnson; John Karat; Thomas M. Ruiz
assignee IBM
A pop-up window describes valid choices for user input.

4,653,020
Display of multiple data windows in a multi-tasking system
filed 10/17/83
granted 3/24/87
inventors Harry Cheselka, Jeffrey S. Lucash, William R. Vincent
assignee IBM
Apparently covers windowing.

4,656,582
Generating storage reference instructions in an optimizing compiler
filed 2/4/85
granted 4/7/87

4,656,583
Method for improving global common subexpression elimination and code
motion in an optimizing compiler
filed 8/13/84
granted 4/7/87
owned by IBM

4,667,290
Compilers using a universal intermediate language
filed 9/10/84
granted 5/19/87

4,672,575
Schematic building cursor character
filed 5/31/83
granted 6/9/87
inventor Lawrence K. Stephens
assignee IBM
Abstract:  "A personal computer having an interactive all points
addressable display thermal and a cursor positioning device is provided
with apparatus for facilitating the generation of a graphics display.  At
least one table of selectable cursor characters is stored in memory, and
from this table, any character can be selected to be the cursor character.
The selected character is displayed as the cursor and movable to any point
on the all points addressable display by the cursor positioning device.
Once the current cursor character is at a desired point on the display, it
is fixed in that position by reading the position and cursor data into the
display buffer of the display terminal."
First claim:
1. A computer system for providing an interactive graphics display comprising:
- means for providing a table of selectable cursor graphics characters;
- means for selecting one of said cursor graphic characters as the current
cursor symbol
- means for displaying the selected cursor graphic character
- means for moving the displayed cursor graphic character on said
means for displaying; and
-means for fixing an image of the currently displayed cursor graphic
character on the said means for displaying at one of more locations to
generate a graphic display, said means for moving thereafter being capable
of moving the currently displayed cursor graphic character to another
location on said means for displaying.

4,674,040
Merging of Documents
granted 6/16/87
assignee IBM
This is the so-called "include file patent".  It is cited in Brian Kahin's
article, "The Impact of Software Patents," in the Winter 1989 issue of the
EDUCOM Review (Vol. 24 No. 4).
Abstract:  "A method of, an system for, merging a portion of one document
into another and providing for current viewing and on line editing.  During
preparation of a document, a paragraph from another document can be
included in the document being prepared by referencing the other document
and paragraph.  The result of referencing is inclusion of the paragraph, a
view of the document being prepared, and a document including the included
paragraph which is dynamically editable.  If the paragraph is edited, an
operator decision is to be made as to whether the other document is to be
updated according to the editing."
Claim 1 is:
"A method for merging a portion of one document into another document, said
method comprising:
(a) including a reference to said another document to said portion; and
(b) causing said portion to be merged with said another document and
displayed in merged form."
It covers displaying part of one document within the display of another, in
response to a kind of cross-reference.  This is, of course, a basic idea of
hypertext.  So many hypertext systems would infringe this patent.

4,687,353
Automatic format, mode control and code conversion for data processing and
printing apparatus
filed 4/28/86
granted 8/18/87
inventor Peter J. DeGeorge, Roger F. Ross, Donald E. Sims
assignee IBM
from the abstract:  "The invention concerns itself primarily with the
handling of left margins and indentation levels for different paragraphs in
a document especially when a document under preparation has line lengths of
an original document that was prepared concurrently with the storage of the
coded signals on the record media."
The patent appears to be on printing a document with different indentation
than it is stored with; a suggested implementation is tabbing from the left
margin before beginning to print each line.

4,714,918
Window view control
filed 4/30/84
granted 12/22/87
inventors Barbara A. Karker, Irene H. Herna'ndez
assignee IBM
abstract:  "A method of, and system for, controlling a view f window
information upon editing the information.  The view is controlled  based on
mode selection.  For normal information input operations, information
scrolling is selected.  Related existing information adjacent the newly
input information will be viewable, but remote information will eventually
be scrolled out of the window.  For those instances where all existing
information is to remain viewable upon input of additional information,
border scrolling will result in a varying of the size of the window."

4,736,308
Search/retrieval system
filed 7/10/85
granted 4/5/88
inventor Paul Heckel
assignee Hyperracks Inc.
A system allowing parts of multiple cards to be displayed on the screen at
the same time.  Apple was sued over hypercard on the basis of this patent,
but settled.

4,736,866
Transgenic non-human mammals
filed 6/22/84
granted 4/12/88
Harvard's mouse patent

4,742,450
Method to share copy on write segment for mapped files
filed 2/16/86
granted 5/3/88

4,777,593
Vector processing apparatus including means for identifying the occurrence
of exceptions in the processing of vector elements
filed 12/21/84
granted 10/11/88
inventor Yaoko Yoshida
assignee Hitachi, Ltd.
Abstract:  "A vector processing apparatus has a number of pipeline
arithmetic units operating concurrently to execute a set of vector
instructions dealing with vector elements.  Stack registers are provided
for each arithmetic unit to hold the vector instruction address, leading
vector element position and vector register internal address, so that one
of the exceptions that can be detected successively by several arithmetic
units during the process of the vector instructions is selected on a
priority basis through the comparison of information in the stack of the
currently detected exceptions with information of exception detected
previously."

4,814,746
Data compression method
filed 8/11/86
granted 3/21/89
inventors Victor S. Miller, Mark N. Wegman
assignee IBM
This was applied for after 4,558,302 (the LZW patent), but their methods
are identical.
abstract:  "Communications between a Host Computing System and a number of
remote terminals is enhanced by a data compression method which modifies
the data compression method of Lempel and Ziv by addition of new character
and new string extensions to improve the compression ratio, and deletion of
a least recently used routine to limit the encoding tables to a fixed size
to significantly improve data transmission accuracy."

4,815,029
In-line dynamic editor for mixed object documents
filed 9/23/85
granted 3/21/89
inventors Barbara A. Barker, Irene H. Hernandez, Beverly H. Machart
assignee IBM
abstract:  "A method for the intelligent, in-line, dynamic editing of
documents containing mixed object types on a computer work station is
disclosed.  The mixed object types may be text objects, draw graphics
objects, business graphics objects, and tables objects.  The editor
executes actions on use selected objects and attributes based on internal
knowledge of the object type selected rather than by explicit user
commands.  This procedure provides a simple user interface that makes
manipulation of objects and attributes and command execution transparent to
the user.

4,856,787
Concurrent game network
filed 5/3/88
granted 8/15/89
inventor Boris Itkis
assignee Yuri Itkis
Obvious slave-master scheme for playing poker, bingo, blackjack, and keno;
one computer runs the game, the others have touch-sensitive screens for
input.

4,864,501
Word annotation system
Filed 10/7/87
Granted 9/5/89
Assignee Houghton Mifflin Company
Inventors Henry Kucera, Alwin B. Carus
Storing words in a dictionary.

4,864,502
Sentence analyzer
Filed 10/7/87
Granted 9/5/89
Inventors Henry Kucera, Alwin B. Carus
Assignee Houghton Mifflin Company
Parses sentences into parts of speech.

4,864,503
Method of using a created international language as an intermediate pathway
in translation between two national languages
Filed 2/5/87
Granted 9/5/89
Assignee Toltram, Ltd.
Inventor Bruce G. Tolin
Use of interpretive steps instead of strict word-for-word translation.
Rudy Zalesak <zalesak@bme.unc.edu> says:
This patent covers translating texts in one language into Esperanto (or ANY
other "simplified" language) and translating that text into some other
language.
The patent text has to be seen to be believed.  Implementation details
consist of flow charts with labels like Sen Parse and Verb Conjugations.
Nothing in it could be remotely useful to anyone working in natural
language translation (unless it had never occurred to them that they had to
parse sentences first...) Essentially the owners of the patent (Toltran,
Ltd., Barrington Ill.) have a monopoly on an obvious idea that has occurred
to anyone who has thought for a few minutes about machine language
translation.  (And, yes, it had occurred to me also, long before I knew
about this patent).
The patent text is useful for pointers to earlier patents- US Patent
4,502,128 seems to cover word-by-word translation and look-up of parts of
speech, together with rearrangement by target language syntax.  4,456,969
seems to cover spelling checkers for multi- lingual documents.
Just stating the idea seems enough to implement it: most readers of this
post could make a prototype "multi-lingual spelling checker" in a few days,
given a few machine-readable language dictionaries. Someone might object
that "it's more complicated than that"; real spelling checkers have all
kinds of refinements.  But the patent owners didn't have to make a GOOD
spelling checker either!

4,876,541
Stem [sic] for dynamically compressing and decompressing electronic data
filed 10/15/87
granted 10/24/89
inventor James A. Storer
assignee Data Compression Corporation
LZW-based, with "all-prefixes" addition.
Encoder and decoder include dictionaries which may be modified (new strings
added and infrequently used ones removed).  The abstract never uses the word
"algorithm" without prepending a modifying "novel".
James Woods <jaw@ames.arc.nasa.gov> says (and Dan Bernstein
<brnstnd@KRAMDEN.ACF.NYU.EDU> confirms) that this was independently
discovered by Dan Bernstein of NYU a year later, and by Nigel Horspool of
the Univertity of Vicotria; Horspool published in DCC '91.

4,893,256
Interactive video composition and presentation systems
filed 4/4/85
granted 1/9/90
inventors Charles T. Rusherford, Nancy S. Frank
assignee IBM
Abstract:  A method for specifying and execting independent, multi-media
tasks along a synchronizing time-line, preferably in the form of a
spreadsheet matrix with the event elements making up the rows and the time
periods the columns.  The media include various pieces of hardware such as
touch screens, voice synthesizers, viedeo disk players, and the like.  In
designing a presentation, the author types into the matrix indications of
which piece of hardware will be operating and for what specified period of
time during the presentation.  This information is also accessible to all
other events in the presentation thereby allowing complex multi-media
presentations to be designed by a user who is relatively unsophisticated in
using computers.
Includes 400 pages of source code.

4,956,809
Method for canonical ordering of binary data for portable operating systems
filed 12/29/88
granted 9/11/90
assignee Mark Williams Co, Chicago, Ill.
inventors Johann George, Trevor J. Thompson, David G. Conroy, Frederick H. Tudor
Covers using a single standard byte ordering (say, big-endian or little-endian)
for transfer of data between machines whose normal byte ordering is different.
Paul Eggert <eggert@twinsun.com> says:
This patent, on network byte ordering, covers any file header that tells
you the endianness of the file.

5,012,231
Method and apparaus [sic] for cursor motion having variable response
filed 10/20/88
granted 4/30/91
assignee Glemics, Inc., Berkeley, California
inventor Lee Felsenstein
Abstract:
A method and apparatus for controlling the movement of cursor indicia on
display screens is disclosed in which the parameters of the equations of
motion used to translate signals originating from positioning actuators
into movement of the cursor may e varied.  Factors such as the rate of
change of the actuation signal, position of the cursor on the display
screen, voluntary control input from the operator, and conditions
determined by application software may be used to vary these parameters.

5,031,134
System for evaluating multiple integrals
filed 3/27/90
granted 7/9/91
inventors Wilfred Kaplan, Frederick B. Sleator
assignee The University of Michigan
Abstract:  "A system for computing multiple integrals employs an algorithm
which selects a plurality of predetermined parameters, corresponding to
selectable levels of accuracy of an approximation at the solution.  The
parameter values are selected and stored, along with a smoothing index,
which may be zero.  An arithmetic logic unit, which can perform a variety
of functions under control of an instruction decoder, forms a plurality of
functions in the form of unique polynomials, under predetermined
conditions, such that a value can be determined for the multiple integral.
The parameters are selected in response to a judgment on the part of the
user of a required minimum level of accuracy in the context of the
increases in computing time which would be required to achieve higher
levels of accuracy."


===========================================================================

We don't have copies of the following patent disclosures.
Patent disclosures can be acquired by sending $1.50 per patent to 
Patent and Trademark Office
Washington, D.C. 20231

We don't have a copy of:

2,552,629
Rudy Zalesak <zalesak@bme.unc.edu>, citing Carl Oppedahl, says:  This
patent covered Hamming codes for error correction as implemented in
electric switching circuits; the Bell System was forced to make it
available for royalty free licensing in 1956 as a result of an antitrust
case. Details Sphere-Packing to Simple Groups>>, MAA, 1983.

3,380,029
Sorting System
granted 4/23/68
assignee Applied Data Research, Inc.
inventor Martin Goetz
Earliest US software patent?

3,405,457
owned by the University of Illinois
The PLATO patent, now expired.  
One of its claims covered the use of a single computer to serve the
independent needs of multiple interactive users.  That is, it covered all
timesharing systems.

4,200,770
Cryptographic Apparatus and Method
filed 9/6/77
granted 4/29/80
inventors Hellman, Diffie, Merkle
assignee Stanford University
Exponential, and all other forms of, secret key exchange.
This is the "Diffie-Hellman" patent.
Public Key partners has exclusive sublicensing rights.

4,218,582
Public Key Cryptographic Apparatus and Method
filed 10/6/77
granted 8/19/80
inventors Hellman, Merkle
assignee The Board of Trustees of the Leland Stanford Junior University
Knapsack, and all other forms of, public key cryptography.
This is the "Hellman-Merkle" patent.
Public Key partners has exclusive sublicensing rights.

4,398,246
Word Processing System Employing a Plurality of General Purpose Processor
Circuits
filed 1980-08-12
granted 1983-08-09
assignee Pitney Bowes Inc.
Irlam says:
A collection of possibly diskless computers connected in a network so as
to share resources.  (I am having some difficulty understanding exactly
what is claimed - I think the system is limited to performing word processing
and one of the computers must have a single line display, but I am not
certain).

4,405,829
Cryptographic Communications System and Method
filed 12/14/77
granted 9/20/83
inventors Ronald Rivest, Shamir, Adleman
assignee Massachusetts Institute of Technology
The RSA public key cryptosystem, and any communication system that evaluates
a polynomial modulo a prime number.
This is the "RSA" patent.
Public Key partners has exclusive sublicensing rights.

4,424,414
Exponential Cryptographic Apparatus and Method
filed 5/1/78
granted 1/3/84
inventors Hellman, Pohlig
assignee Board of Trustees of the Leland Stanford Junior University
A conventional cryptosystem that performs modular exponentiation.  Not as
important as the other 3 cryptography patents (Diffie-Hellman,
Hellman-Merkle, and RSA).
This is the "Hellman-Pohlig" patent.
Public Key partners has exclusive sublicensing rights.

4,434,753
Register Allocation System Using Recursive Queueing During Source Code
Compilation
granted Mar 6, 1984
inventor J. Rizzi
assignee International Business Machines Corporation

4,455,025
Owned by FortuNet -- relates to 4,856,787 and coputer game networks.

4,456,969
Rudy Zalesak <zalesak@bme.unc.edu> says:
Seems to cover spelling checkers for multi- lingual documents.

4,458,311
"text and numeric processing on same screen"

4,486,857
granted 12/84
inventor Paul Heckel
Hyperracks Inc.
A file system of more than one card, each with multiple fields, where all
the fields can be scrolled independently.  Apple was sued over this and
settled, licensing it.

4,502,128
Rudy Zalesak <zalesak@bme.unc.edu> says:
Seems to cover word-by-word translation and look-up of parts of
speech, together with rearrangement by target language syntax.

4,555,771
Data Processing System for Data Base Management of Matrix Type Data
filed 1982-03-26 (originally filed 1979-08-27)
granted 1985-11-26
assignee Fujitsu
Irlam says:  A technique for managing a database with more than one index.  ???

4,555,772
filed 5/31/83
assignee IBM
Supposedly "multiple cursors for multiple windows, using an XOR-writing technique"

4,567,574
Optimizing COBOL Object Code Instruction Path Length with respect to
PERFORM Statements
granted Jan 28, 1986
inventor H. Saade, W. Tindall
assignee International Business Machines Corporation

4,571,678
Register allocation and spilling via graph coloring
filed 11/5/82
granted 2/18/86.
Owned by IBM.  Inventor is Gregory Chaitin from Yorktown Heights, NY.
It's one of a group of 16 or so patents filed by IBM as result of their
801/PL.8 development.  They also mention things like global common
subexpression elimination and optimization of array bounds checking.
John R. Levine <johnl@iecc.cambridge.ma.us> says:
Covers the compiler technique of allocating registers by graph coloring,
with a spill algorithm to handle cases where the original graph is not
colorable.  Chaitin had already published a coloring algorithm, but the
patented spill modification is needed to make it practical.

4,611,277
filed 15 Sep 83
granted 9 Sep 86
inventors Kemppainen et al.
assignee BankAmerica [or is that Bank of America?]
John R. Levine <johnl@iecc.cambridge.ma.us> says:
It is 200 pages long, consisting mostly of a long Basic program.  The
patent is for the rather obvious idea of having a microcomputer call up a
mainframe and download cash management or bank account data, something a
friend of mine did at about the same time for someone else as a quick hack.
Luckily, BofA seems not inclined to enforce this one.
The patent claims are so broadly worded that they look to me like they
cover any use of a microcomputer to download data from a mainframe:
1.  A communications system comprising:
a user terminal including
a microcomputer,
a mainframe computer connected to said microcomputer, said user terminal
further including communication software control means for controlling the
transfer of data directly between said microcomputer and said mainframe
computer, said sofware control means including means for controlling the
transfer of said data in an unattended mode.
2.  A system as in claim 1 wherein said software control means include
means for controlling the transfer of said data in an automatic mode.
3.  A system as in claim 1 wherein said software control means include
means for controlling the transfer of said data in a manual mode.
4.  A system as in claim 1 wherein said software control means include
means for controlling the transfer of said data in a terminal emulation
mode.
(Claims 5-9 relating to cash management applications of the same things)

4,624,462
Owned by FortuNet -- relates to 4,856,787 and coputer game networks.

4,646,256
Computer and Method for Solving the Discrete Bracewell Transformation
granted 1987
Stanford University
inventor Ronald N. Bracewell
Can be used in many fields to more quickly analyze data by computers.

4,648,044
Technowledge Inc.
Supposedly on "basic AI techniques"

4,648,067
Footnote management for display and printing
granted 3/3/87

4,648,071
Designation of footnotes and footnote reference
granted 3/3/87

4,656,582
Generating Storage Reference Instructions in an Optimizing Compiler
granted Apr 7, 1987
inventor G. Chaitin, M. Hopkins, P. Markstein, H. Warren, Jr.
assignee International Business Machines Corporation

4,656,583
Method for Improving Global Common Subexpression Elimination and Code
Motion in an Optimizing Compiler
granted April 7, 1987
inventor M. Auslander, J. Cocke, P. Markstein
assignee International Business Machines Corporation

4,656,602
Method of control placement of image of document to be printed on paper in
an interactive text processing system
granted 4/7/87

4,674,042
Editing business charts
granted 6/16/87

4,701,848
System for effectively paralleling computer terminal devices
granted 10/20/87
assignee Clyde, Inc.
inventor Robert A. Clyde
Bruce Orchard <orchard@engr.wisc.edu> says:
This describes how in VMS to make the output destined for one terminal to
appear on two terminals and to make the input from two terminals appear to
have come from one terminal.
The existence of this patent came to light when Clyde asked DECUS to remove
the WATCH program from the DECUS program library.  Clyde ultimately backed
down.

4,710,872
Method for Vectorizing and Executing on an SIMD Machine Outer Loops in the
Presence of Recurrent Inner Loops
granted Dec 1, 1987
inventor R.G. Scarborough
assignee International Business Machines Corporation

4,714,989
Functionally structured distributed database processing system
filed 10/20/86
granted 12/22/87
inventor Roger E. Billings
Covers a central database server (used like a file server) connected to
user stations via a network.
The American Academy of Science (to whom it was given in return for a
fraction of the proceeds) sued Novell and Bank America for (respectively)
writing and using a distributed database system that ran on a local area
network.
We have the first page.

4,718,008
filed 16 Jan 88
granted 5 Jan 88
inventors Chang et al.
assignee IBM
John R. Levine <johnl@iecc.cambridge.ma.us> says:
The method used to handle page faults in critical sections by backing out
the critical section code.  References patent 4,730,249.

4,730,249
filed 16 Jan 86
granted 8 Mar 88
inventors O'Quin II et al.
assignee IBM
John R. Levine <johnl@iecc.cambridge.ma.us> says:
The method used for handling virtual memory segments in AIX on the IBM RT
PC, involving a software implementation of two-level pagable page tables.
Hard to say how obvious it is, though the implementation is somewhat
specific to the reverse map MMU used in the RT PC and RS/6000.

4,740,904
Line Following System and Process
filed 11/1/85
granted 4/26/88
inventor John Nagle
Covers "auto-tracing" of raster images into vector images.  Licensed
to Autodesk, Inc.

4,742,447
filed 16 Jan 86
issued 3 May 88
inventors Duvall et al.
assignee IBM
John R. Levine <johnl@iecc.cambridge.ma.us> says:
The method for handling mapped files in the two level Unix/VRM operating
system on the RT.  (Uses the name Unix in the claims.)  Written broadly
enough that the SVR4 disk I/O system might infringe, though since AT&T and
IBM have cross-licenses it hardly matters.

4,744,028
Method and Apparatus for Efficient Resource Allocation
granted 1988
Bell Laboratories
inventor Narendra K. Karmarkar
Can help airlines schedule planes and crews more efficiently.
Is this the linear programming patent?

4,752,877 4,722,055 4,642,768
Patents on a computer system that calculates the amount required for one
year at a particular college, informing parents how much to deposit to
guarantee that a year's tuition, some years down the road, will be covered.
Upheld in court.

4,768,159
Squared Radix Discrete Fourier Transform
granted 1988
owner TRW
Computer system similar to the Discrete Cosine Transform (see 4,797,847).

4,773,007
Compiler Code Optimization Method for a Source Program Having a First and
Second Array Definition and Use Statements in a Loop
granted Sep 20, 1988
inventor Y. Kanada, K. Isida
assignee Hitachi, Ltd.

4,782,444
Compilation Using Two-Colored Pebbling Register Allocation Method Such
That Spill Code Amount is Invariant With Basic Block's Textual Ordering
granted Nov 1, 1988
inventor A. Munshi, K. Schimpf
assignee International Business Machines Corporation

4,783,761
Spelling Check Dictionary with Early Error Signal
granted  8 Nov 1988
filed  26 Dec 1985
assignee  Smith Corona Corporation, Cortland, New York
inventors  Gray, R. William, Ithaca, New York; Adams, Donald T., Homer, New
York; Duncan, IV, Howard C., Marathon, New York
Early check for misspelling:  an error signal is emitted "upon the
earliest determination that an input character does not conform to
that of any word listed in the dictionary".
Patent text is online.

4,797,729
System Incorporating an Error-tolerant Picture Compression Algorithm
owner Eastman Kodak
Can minimize distortions when pictures are stored in computers.

4,797,847
Discrete Cosine Transform
granted 1989
inventor Pierre Duhamel of France
Can help send electronic signals more rapidly and store video data more
compactly.

4,807,182
Apparatus and Method for Comparing Data Groups
dated Feb 21, 1989
inventor Cary L. Queen
owned by Advanced Software, Inc. of Sunnyvale, California.
Patent on comparing text blocks by comparing hash codes and for displaying
the differing sections in two windows on one CRT ("or other suitable
device").  This covers the diff program.

4,821,181
Method for Converting a Source Program of High Level Language Statement into
Object Program for a Vector Processor
granted	Apr 11, 1989
inventor K. Iwasawa, Y. Tanaka
assignee Hitachi, Ltd.

4,823,108
An Improved Display System and Memory Architecture and Method
granted 4/18/89
Quarterdeck Office Systems, Inc.
Someone (Kahin?) says:
An improved system for displaying images in "windows" on a computer screen.
Dandekar (who claims the patent was grated June 1989) says:
Quarterdeck patents the multitasking DESQview environment specific process
-- a method of dealing with ill-behaved software that circumvents the
operating system for its displays, allowing it to work properly in a
multitasking environment.

4,833,606
Compiling Method for Vectorizing Multiple DO-Loops in Source Program
granted May 23, 1989
inventor K. Iwasawa, Y. Tanaka
assignee Hitachi, Ltd.

4,885,684
Method for Compiling a Master Task Definition Data Set for Defining the
Logical Data Flow of a Distributed Processing Network
granted Dec 5, 1989
inventor E. Austin, J. Robertson
assignee International Business Machines Corporation

4,891,503
filed 29 Mar 88
issued 2 Jan 90
inventor Tmomas Jewell
assignee Gascard, Inc.
John R. Levine <johnl@iecc.cambridge.ma.us> says:
A distributed credit card authorization scheme that caches part of the
"deny" file in the terminals to speed up transactions.  Looks pretty obvious
to me to anyone who knows anything about caches.

4,908,861
Data Authentication Using Modification Detection Codes Based on a Public
One Way Encryption Function
inventors D. Coppersmith, S. Pilpel, C. H. Meyer, S. M. Matyas, M. M.
Hyden, J. Oseas, B. Brachti, and M. Schilling
assignee IBM
granted March 13, 1990

4,914,590
granted April 3, 1990
assignee Planning Research Corporation (PRC)
This is a patent on a NLP (natural language processing) technique.  It is
written so generally as to apply to any parsing technique that uses a
lexicon, a grammar, and a canonical semantic representation that encodes
case (modal) information.  (Since natural languages use case, and the case
is semantically significant (cf. modal logic), this isn't a significant
restriction.)  The claim in question is so general that, were it not
explicitly limited to "natural language text," it would appear to apply to
all compilers of any sort.  So in effect, the entire act of parsing a
natural language, at least as it is practiced today, does appear to be
barred by this patent.

4,916,610
Multilanguage software integration through preprocessing
granted 10 April 1990
assignee Racal Data Communications Inc., Sunrise, Florida
ABSTRACT:
A method of assuring consistency of constants in a multilanguage software
system, includes generating a first set of code written in a first language
using a plurality of symbolic constants to represent a corresponding
plurality of actual constants. A second set of code is written in a second
language using the plurality of symbolic constants to represent the
corresponding plurality of actual constants. A common header file is
generated which contains information which relates the plurality of
symbolic constants to the corresponding plurality of actual constants. The
header is included within the first and second sets of code. The symbolic
constants in the first and second sets of code are replaced with their
corresponding actual constants during a preprocessing step. Any constructs
which are not a part of the first language are stripped from the second set
of code including the header file. Any constructs which are not a part of
the second language are stripped from the first set of code including the
header. The resulting files have their symbolic constants consistently
replaced by constants which are defined in the header so that changes need
only be made in the header file to assure consistency in the several
languages.

4,918,722
Control of Electronic Information Delivery
filed May 11, 1988
granted Apr 17, 1990
assignee Brooktrout Technology, Inc
Stuart Lynne <sl%wimsey.bc.ca@metro.ucc.su.OZ.AU> says:
Abstract:
Delivery of binary encoded character data and facsimile encoded data to a
specified recipient is controlled rapidy, simply and with versatility, by
e.g., DTMF commands sent by a user.
This patent purports cover use of DTMF (touch tones) to control a remote
system to send facsimilies. E.g. phone into a voice retrieval system, select
a document and enter a fax phone number to have it faxed to you. Or upload a
fax and have it forwarded to a specified phone number.
[Steve Elias <eli@spdcc.com>, former Brooktrout employee, says:  the latter
"upload fax thang" is NOT covered by this patent.]
The patent was filed in May 1988. I have in my possesion a brochure
from Telecom Canada dated Jan. 1988, describing their fax forwarding
service. Specifically you dial into one of their fax numbers, identify
yourself with a code and PIN, select a command, optional arguements (such as
phone numbers to forward to) and then upload a fax. It then redirects your
fax to the numbers specified. [Their target market at the time was to save
you money when sending faxes to oversea's numbers.]
The Telecom service was fielded and running in January of 1988. Given the
length of time for a common carrier to develop and institute a service of
this type (and get government approval etc) it would seem that we have amply
evidence of prior art to invalidate this patent that was in place well in
advance of filing.
[Steve Elias says:  the Telecom Canada thang you mention here covers
uploading faxes and redirecting them.  the Brooktrout patent does NOT cover
such functionality.  i believe that a Japanese company owns a patent which
covers the upload/redirect fax thang.]

4,931,783
Owned by Apple.
Appears to cover Macintosh "tear-off" menus.
Abstract:
The method generates and displays the menu bar having the command option.
A cursor is positioned on the display using a cursor control.  The
manipulation of the cursor results in a corresponding movement of the
cursor on the display.  The menu window is displayed by selecting command
option.  The command option is selected by the user's control of a signal
generator being coupled computer controlled display system.  The menu
window is removed from the menu bar while the menu window is displayed by
manipulating the cursor control so as to move the cursor across the border
the menu window may be removed from the menu bar.

4,939,354
Dynamically variable machine readable binary code and method for reading
and producing thereof
waters@nddsun1.sps.mot.com says:
The startup company Datacode International Inc exists to market this
patent.  THe patent covers a new form of marking code, somewhat like the
UPC barcodes on retail products. The invention includes the format of the
code, as well as the software used to generate and read the code. No
hardware involved in the "novelty of the device" - all standard "off the
shelf" stuff.  At least one company that would not exist without what I at
least class as a software patent.

4,943,869
Compression Method for Dot Image Data
filed 1988-05-04
granted 1990-07-24
assignee Fuji Photo Film Co.
Lossy and lossless image compression schemes.

4,943,909
inventor Alan Huang
assignee AT&T
A method, based on origami, of allocating processors to parts of a problem
(say, an aerodynamic analysis).

4,955,066
Filed: 1989-10-13
Granted: 1990-09-04
Inventor: Notenboom, L.A.
Owner: Microsoft
Title: Compressing and Decompressing Text Files
[Noted in signon screen of Word 5.5 and on the outside of the MS-DOS 5.0
Upgrade.]
Jean-loup Gailly <jloup@chorus.fr> says: a method of data compression using
run-length encoding, 'key phrase' and huffmann coding.
Abstract:
A method of compressing a text file in digital form is diclosed.
A full text file having characters formed into phrases is provided by an
author.  The characters are digitially represented by bytes.  A first pass
compression is sequentially followed by a second pass compression of the
text which has previously been compressed.  A third or fourth level of
compression is serially performed on the compressed text.  For example, in
a first pass, the text is run-length compressed.  In a second pass, the
compressed text is further compressed with key phrase compression.  In a
third pass, the compressed text is further compressed with Huffman
compression.  The compressed text is stored in a text file having a Huffman
decode tree, a key phrase table, and a topic index.  The data is
decompressed in a single pass and provided one line at a time as an output.
Sequential compressing of the text minimizes the storage space required for
the file.  Decompressing of the text is performed in a single pass.  As a
complete line is decompressed, it is output rapidly, providing full text to
the user.

4,956,791
Merging Pattern-Matching Networks Including Retes
filed 1988-11-14
granted 1990-09-11
assignee IBM
Technique for merging pattern recognition networks without the need to
recompile the entire resulting network.

4,956,806
Method and Apparatus for Editing Source Files of Differing Data Formats
Using an Edit Tracking File
filed 1988-07-12
granted 1990-09-11
assignee IBM
Storing the edits applied to one sound or image file and subsequently
applying them to a second file.

4,965,724
Compiler System Using Reordering of Microoperations to Eliminate
Interlocked Instructions for Pipelined Processing of Assembler Source Program
granted Oct 23, 1990
inventor I. Utsumi, Y. Mori
assignee Oki Electric Industry, Ltd.

4,975,950
System and Method of Protecting Integrity of Computer Data and Software
inventor Stephen A. Lentz
filed November 3, 1988
David.M.Chess <CHESS@YKTVMV.BITNET> says:
It basically patents the idea of having a virus-checker get control before
the operating system, and not allowing boot if it finds a virus.  One
sample PC implementation is code in an additional ROM module (on a "virus
protector board") that would get control during boot (like the hard disk
BIOS, the EGA BIOS, and so on), and load and test "the system files" (not
clear if he means the boot records, or things like IBMBIO, IBMDOS,
COMMAND.COM), and not allow boot if a virus was found (how it tells isn't
spelled out).  This is just one sample implementation; the actual claims
are quite broad, and seem to cover anything that gets control between the
"program for controlling said central processing unit" and the "program for
interfacing said storage memory with said system", by which he presumably
means ROM-like things and operating-system-like things.

4,979,832
Dynamic Substitution Combiner and Extractor
granted Dec. 25, 1990
inventor Terry Ritter

4,995,075
Rudy Zalesak <zalesak@bme.unc.edu> says:
An article in the November 1991 <<Discover>> magazine states that two
psychologists at AT&T Bell Labs have a technique for using musical tunes to
individualize phone rings. The article mentions a "patent on the software";
just what might be covered is not clear.  It is hard to believe that
pairing a stored employee phone ID with a given musical tune would involve
a novel technique.  Most of the work (taking two years, although it doesn't
say that this project was their only occupation during that time) seems to
have involved testing out various ringing styles on volunteers. For example
they discovered that people became aggravated at "rings" that called their
name!

5,001,478
Method of Encoding Compressed Data
filed 1989-12-28
granted 1991-03-19
inventor Michael E. Nagy
assignee IBM
1. A method of encoding a compressed data stream made up of a sequence of
literal references, lexicon references and history references, which
comprises the steps of:
assigning to each literal reference a literal identifier;
assigning to each history reference a history identifier;
assigning to each lexicon reference a lexicon identifier;
and emitting a data stream with said identifiers assigned to said references.
Gordon Irlam <gordoni@cs.adelaide.edu.au> says:
The invention can probably be best understood by considering the
decompressor.  It consists of a history buffer, and a lexicon buffer, both
of which are initially empty.  The history buffer contains the last n
symbols emitted.  Whenever a history buffer reference is to be output the
string so referenced is subsequently moved to the lexicon buffer for future
reference.  Thus the history buffer keeps track of strings that may be
repeated on a very short term basis, while the lexicon buffer stores items
for a longer time.  Furthermore a history reference involves specifying
both the offset and length within the history buffer, whereas a lexicon
reference simply specifies a number denoting the string.  Both buffers have
a finite size.
I don't know all that much about compression, but this seems to me to be
fairly general, and a quite trivial thing that is being patented.  It also
seems that the compressor would not be all that efficient (at least in the
preferred embodyment, which amongst other things doesn't appear to attempt
to encode the lexicon references on the basis of their frequency of
occurrence).  Presumably speed is the main objective.
It sounds to me like the sought of thing a student might come up with given
one lecture on data compression, and then asked to write a compression
program.
Jean-loup Gailly <jloup@chorus.fr> says:
The concept of history buffer is definitely not new, this is the LZ family
of algorithms. The concept of lexicon is not new either, there are many
papers published on this. The US patent office probably considered that
just combining two old ideas in one algorithm was patentable.

5,031,134
inventors Wilfred Kaplan and Frederick B. Sleator
Modified Monte Carlo technique for calculating volume.
Reported by Edmund L. Andrews in "Patents" column of New York Times, July
26, 1991.

5,036,535
Carl M. Kadie <kadie@cs.uiuc.edu> says:
Note <NB910812.6@clarinet.com> in clari.nb.telecom says that Unifi
Communications has gotten patent number 5,036,535 for its "PhoneServer
software technology".
"The patent covers both a concept and its implementation in software.
PhoneServer lets telecommunications managers use Unix or Windows 3.0
based computers on their own premises to program and control call
routing in the public network."
"'The patent covers both the concept of what we have done as well as
the implementation, and the concept is a big part of the patent,' Bob
Pokress of the company told Newsbytes."
Here is the end of the note:
"(Dana Blankenhorn/19910812/Press Contact: Unifi, Bob Pokress,
508/663-7570)"

5,046,020
Distributed parallel processing network wherein the connection weights are
generated using stiff differential equations
granted Sep. 3, 1991
inventor:  David L. Filkin
Assignee:  E. I. du Pont de Nemours and Company
Abstract:  A parallel distributed processing network of the back
propagation type is disclosed in which the weights of connection between
processing elements in the various layers of the network are determined in
accordance with the set of steady solutions of the stiff differential
equations governing the relationship between the layers of the network.

5,049,881
Apparatus and method for very high data rate-compression incorporating
lossless data compression and expansion utilizing a hashing technique
inventors Dean K. Gibson, Mark D. Graybill
assignee Intersecting Concepts, Inc.
filed 6/18/90
granted 9/17/91
A related patent is Phil Katz, 5,051,745.
Terry Ritter <ritter@cactus.org> says:
This covers LZRW compression algorithms.
Ross Williams also invented this series of algorithms in 1989, and has logs
and listings of this work; he openly published in April 1991.  Gibson and
Graybill's date of invention is not known
Abstract:
A method and apparatus for compressing digital data that is represented as
a sequence of characters drawn from an alphabet. An input data block is
processed into an output data block composed of sections of variable
length. Unlike most prior art methods which emphasize the creation of a
dictionary comprised of a tree with nodes or a set of strings, the present
invention creates its own pointers from the sequence characters previously
processed and emphasizes the highest priority on maximizing the data
rate-compression factor product. The use of previously input data acting as
the dictionary combined with the use of a hashing algorithm to find
candidates for string matches and the absence of a traditional string
matching table and associated search time allows the compressor to very
quickly process the input data block. Therefore, the result is a high data
rate-compression factor product achieved due to the absence of any string
storage table and matches being tested only against one string.
Exemplary Claim:
1. A compression method for compressing a stream of input data into a
compressed stream of output data based on a minimum number of characters
in each input data subblock to be compressed, said compression method
comprising the steps of: a. initializing a hash table and initializing
an SRC pointer; b. processing input data in the order in which the
characters in the data appear and hashing input data subblocks of the
minimum compression size selected; c. maintaining a hash table which
contains at each entry, an SRC pointer which points to a previous
subblock which hashed to this hash table entry, such that the
possibility of any string of data previously occurring in the input
block may be tested by hashing the current subblock to a hash table
entry, obtaining the previous SRC pointer contained in that entry, and
comparing the two strings of data; d. if the two strings of data match
on at least the size of the subblock, then generating a backwards
pointer to the previous occurrence of the same string of data and
thereby compressing the second occurrence of the string of data; e. if
the two strings of data do not match, then storing the string of data as
incompressible data; and f. continuing steps b. through e. until the
entire input data has been processed.

5,051,745
String searcher, and compressor using same
filed  8/21/90
granted 9/24/91
inventor  Phillip W. Katz (author of pkzip)
Jean-loup Gailly <jloup@chorus.fr> says:  covers the idea of using a sorted
hash table to search strings, and data compressors of the LZ77 family using
such a hash table.
ABSTRACT:
Methods and apparatus for string searching and data compression.
In the string search method and apparatus pointers to the string to be
searched are indexed via a hashing function and organized according to the
hashing values of the string elements pointed to. The hashing function is
also run on the string desired to be found, and the resulting hashing value
is used to access the index. If the resulting hashing value is not in the
index, it is known that the target string does not appear in the string
being searched. Otherwise the index is used to determine the pointers which
correspond to the target hashing value, these pointers pointing to likely
candidates for matching the target string. The pointers are then used to
sequentially compare each of the locations in the string being searched to
the target string, to determine whether each location contains a match to
the target string.
In the method and apparatus for compressing a stream of data symbols, a
fixed length search window, comprising a predetermined contiguous portion
of the symbol stream, is selected as the string to be searched by the
string searcher. If a string to be compressed is found in the symbol
stream, a code is output designating the location within the search window
of the matching string and the length of the matching string.

5,083,262
Language bindings for graphics functions to enable one application
program to be used in different processing environments
Gregory Aharonian <srctran@world.std.com> says:
Word of warning to anyone wanting to use graphics binding libraries like
X, PHIGS, PEX, GKS, etc.

Creating a split screen with a hotkey.

Fritz Henglein (henglein@diku.dk) reports perhaps the earliest software
patent, a German patent on stack implementations of programming languages:
Bauer, F. and Samelson, K., "Verfahren zur automatischen Verarbeitung von
kodierten Daten und Rechenmaschine zur Ausuebung des Verfahrens".
Deutsche Patentauslegeschrift 1 094 019.  Anm. (*) March 30, 1957.
Bek. (**) Dec. 1, 1960 
(*) filed
(**) granted ("announced")

Gilbert Hyatt's microprocessor patent
filed 12/28/70
granted 8/30/90

Hayes Microcomputer Products Inc.'s patent on a program to switch its
modems from transmit mode to receive mode.  It won $10 million damages from
three infringing manufacturers who'd reverse-engineered via clean-room
techniques.  The patent is on the use of "+++", sent with a particular
timing that was supposed to be unlikely when those characters were just
part of the text being transmitted by modem.  (That is, sometimes "+++" is
just text passed through, and sometimes it's a command sequence.)  Any
modem that recognizes this command sequence, or uses a similar strategy, is
in violation.

James A. Woods (jaw@riacs.edu (or ames!jaw)) says:
I am investigating, possibly for a case history to be
recycled to USENET, the particulars of data compression patents.
I am aware of the following patents: IBM's Miller-Wegman LZ variant,
those of Telcor and ACT [losing candidates for the British Telecom modem
standard], James A. Storer's work on limited lookahead as explicated in his
text "Data Compression (methods and theory)", Computer Science Press, 1988,
and the various patents pending associated with the Fiala and Greene
CACM article of April, 1989 on textual substitution methods.
If you have any lore, send it this way.

Matt Vea's patent on setting and unsetting a bit in an idle loop to see
whether the CPU is working or idle.  (Applied for 2/86, received before
10/90.)

Nix Thompson <nix@sgi.com> says:
I believe there is a also a patent owned by GE on the "marching cubes"
method of implicit surface rendering.  I think Stellar got sued for
using it in their AVS scientific visualization system, but I don't
know how the suit came out.  The method was also invented at Brown
University before the patent was filed, but not published.

Patent on expanding abbreviations with space character, filed 1984, granted
1988.  XyQuest, Inc. was forced to remove this feature from XyWrite; it had
been added in June 1987.  Emacs has had this feature since the 1970s.

Paul Krause <krausep@sra.com> says that Systems Research and Applications
Program has been threatened over a patent on NLP (Natural Language
Parsing); SRA's company attorney says that NLP patents are being granted at
the rate of about 200 per year.

Dave Goldblatt <daveg@clearpoint.com> is looking for prior art (pre-
10/5/81) to defeat a patent on the ring buffer.  Specifically, the patent
is on the idea of using two circular buffers in commonly addressable memory
to queue pointers to messages (also in shared memory) between two
processors.  One buffer contains messages going in one direction, and the
other buffer contains messages going in the other.  The allegedly inventive
feature is having one of the processors tell the other processor the size
of the ring buffers.

Terence Kelleher <terryk@encore.com> says:  Another modem company, Bizcomp,
held a patent on a mechanism that allowed use of the same serial data wire
for both control characters and data (not transmit vs. receive).  The
patent was not specific to software.  In fact, the Bizcomp mechanism as
described in the patent was TTL hardware.  The patent was on the use of the
line for both data and control codes, and not on the actual mechanism that
switched them.  While researching, we found a prior patent that described a
similar mechanism, issued sometime in the early 60's to Western Union,
where they used a control code to switch teletype's interpretation from
data to control.  In addition, we felt that the use of ESC to prefix
control commands for terminals amounted to the same use.

Philip Resnik <resnik@unagi.cis.upenn.edu> says:  [There may be a patent
on] a learning-related algorithm known as classifier systems, invented by
John Holland of the University of Michigan and described in the books
_Induction_ and (I believe) in _Adaptation in Natural and Artificial
Systems_.  One component of classifier systems is a class of optimization
techniques known as genetic algorithms; stories that Holland was/might be
patenting classifier systems stirred up a lot of discussion among some
people working on genetic algorithms, in mid-1987 or so.

Philip Resnik <resnik@unagi.cis.upenn.edu> says:  Unless I'm mistaken, J.
K. Baker of DRAGON Systems (Cambridge, MA) has patented a speech
recognition algorithm or algorithms.

Adam J Richter <adam@soda.berkeley.edu> says:  I read about Farallon's
behavior in a old issue of Bay Area _Computer Currents_ about two years
ago.  The article was a profile of a bunch of different companies. The
article talked about Farallon having patents that made it impossible for
anyone to build devices that could talk on PhoneNet, and described the
patents as being quite dubious.  The article also said that nobody was
challenging the patents because Farallon was willing to "license the
technology" cheaply.

Bellcore has applied for a patent on its active message system.
Nathaniel Borenstein <nsb@thumper.bellcore.com> says:
The patent isn't actually on active messaging per se.  The patent is on
security aspects of active messaging, as embodied in the ATOMICMAIL
language.  With AMS/Ness, for example, you can send around a program that
deletes all the recipients files, and the only safeguard is that the user
is first asked "do you trust the user you got this from?" -- as if the mail
couldn't just be a forgery anyway!  Unlike previous active messaging
systems, ATOMICMAIL makes active messaging safe enough to consider using it
for real.

Xerox's Ethernet patent.

Rudy Zalesak <zalesak@bme.unc.edu> says:
A patent (pending) for a method of looking up Kanji (Japanese characters)
is announced in an ad for a Mac Japanese-to-English dictionary and
translation aid called KanjiSama. (SANBI Software Company, 3594 Crowell
Ave., Riverside CA 92504, (714) 352-0276). The ad states:
"Includes a completely new kanji lookup mode based on the Kanji
Alphanumeric Code (Kanc), developed by SANBI Software (Patent Pending)."
	Traditional lookup methods (also supported) are by stroke count
and radical (small parts of a character). The stroke count method is the
most common in Western dictionaries. I am not aware of a public standard
called Kanc; I don't know whether or not it is an invention of SANBI.
	 The claims of course cannot be clear from an ad, but as stated it
seems to be a technique that could be carried out in a dictionary and would
certainly not be patentable in that form.  Just what aspect of such a
technique could be innovative? Presumably the actual lookup must use a
standard technique such as hashing, so the novelty must lie in the
ascii-to-Kanji correspondence. This arguably is not a software invention,
so if my guesses about the patent are correct and the patent is granted,
this would represent an extension of software patents into patents on
information transformation in general. Pamela Samuelson's article in ACM
Comm. on software patents already worried about this possibility.

George Battrick <gwb@crosfield.co.uk> says:
Document ISO/IEC JTC1/SC24 N756 refers to an IBM patent on "Language
Bindings for Graphical Functions ... " as being "issued 1-21-92".
Our search in the "Dialog" database for "LANGUAGE()BINDING" has drawn
a blank, so perhaps we have the wrong keywords, or got the year wrong,
or something.  Can anyone provide a proper reference?  I'd like to
know what exactly is being/has been patented here.

===========================================================================

Foreign patents:

British Patent 2,166,627
This appears to cover pull-down menus
Abstract:
A computer controlled display system having a display wherein a plurality
of command options are displayed along a menu bar and sub-command items
corresponding to each option are displayed once said option has been
selected, and including a cursor control means for selectively positioning
a cursor on said display, comprising:  first display means coupled to said
computer for generating and displaying said menu bar comprising said
plurality of command options; signal generation means coupled to said
cursor control means for signalling said computer of an option choice once
said cursor is positioned over a first predetermined area on said display
corresponding to an option to be selected; said first display means
generating and displaying said sub-command items corresponding to said
selected option; signal modification means coupled to said signal
generation means for latering said signal to said computer once said cursor
is positioned over a second predetermined area corresponding to a
sub-command item to be selected; whereby an option and a sub-command item
is selected and executed by said computer.
Carl Oppedahl <0001811496@mcimail.com> says:
What's interesting about this is it claims priority from a U.S. Patent
application, no. 399,704 filed July 19, 1982.  Generally U.S. patent
applications are kept secret, but when Apple applied in Great Britain they
chose to disclose the existence of the U.S. application.

===========================================================================

		 ARTIFICIAL INTELLIGENCE PATENTS FROM 1989
	    Titles as they appear in the Patent Office Gazette
		 Gregory Aharonian <srctran@world.std.com>
		     Source Translation & Optimization

ASSOCIATIVE PROCESSING
.   Set associative memory
.   Adaptive associative-processing optical computing architectures
.   Associative memory system with spatial light modulator and feedback for
        adjustable thresholding and enhancement

BRAIN
.   Non-invasive method and apparatus for modulating brain signals through
        an external magnetic or electric field to reduce pain
.   Method and apparatus for translating the EEG into music to induce and
        control various psychological and physiological states and to
        control a musical instrument
.   Electrical connection device
.   Topographical mapping of brain functionality from neuropsychological
        test results
.   Hearing device

DECISION SYSTEMS

.   Method of detecting boundary structures in a video signal
.   Voice synthesis utilizing multi-level filter excitation
.   Real-time scheduling system
.   Fluid distribution to multiple users through distributed
        intelligence sub-centers
.   Automated production release system
.   Expert system for processing errors in a multiplex communications system
.   Speech recognition system
.   Automatic classification of images
.   Document processing system deciding apparatus provided with
        selection functions
.   Failing resource manager in a multiplex communication system
.   Interactive statistical system and method for predicting expert decisions
.   Decision and implementation system for medical imaging
.   Automated production dispatch system with feedback control
.   Image discrimination with continuous tone area thinning

EXPERT SYSTEMS
.   Coalescing changes in pattern-directed, rule-based artificial intelligence
        production systems
.   Interactive transector device commercial and military grade
.   Editor for expert system
.   Parser for natural language text
.   Expert system shell for building photofinishing diagnostic systems
.   Expert system with three classes of rules
.   Knowledge system with improved request processing
.   Expert system for processing errors in a multiplex communications system
.   Failing resource manager in a multiplex communication system
.   Interactive statistical system and method for predicting expert decisions
.   Expert vehicle control system
.   Data-driven, functional expert system shell
.   Domain independent shell for building a diagnostic expert system
.   System and method for network configuration

FUZZY LOGIC
.   Powder weighing mixer and method thereof
.   Fuzzy logic computers and circuits
.   Method of and apparatus for measuring liquid
.   Auto-tuning controller using fuzzy reasoning to obtain optimum
        control parameters
.   Fuzzy logic semifinished integrated circuit

IMAGE ANALYSIS
.   Digital image analysis system
.   Full page graphics image display data reduction
.   Self referencing ambiguity free holography
.   Method and method and apparatus for control of light intensity for
        image analysis
.   Apparatus and method for electronic analysis of test objects
.   System and method for determining orientation of planes of imaging
.   Method and apparatus for contextual data enhancement
.   Vision system for distinguishing touching parts
.   DC artifact removal in magnetic resonance imaging
.   Motion analysis tool and method therefor
.   Method for enhancement of ultrasonic image data

INFERENCE
.   Accompaniment line principal tone determination system
.   Expert system with three classes of rules
.   Powder weighing mixer and method thereof
.   Using infrared imaging to monitor and control welding
.   Fuzzy logic computers and circuits
.   Method of and apparatus for measuring liquid
.   Data-driven, functional expert system shell
.   Reasoning system for reasoning with uncertainty
.   Inference system
.   Method for controlling operation of a blast furnace

KNOWLEDGE REPRESENTATION
.   Automated defect recognition system
.   Autonomous resource management system with recorded evaluations of
    system performance with scheduler control including knowledge
    learning function
.   Expert system shell for building photofinishing diagnostic systems
.   Knowledge system with improved request processing
.   Document filing system with knowledge-base network of concept
    interconnected by generic, subsumption, and superclass relations
.   Knowledge-based system having plural processors
.   Method for controlling operation of a blast furnace

LANGUAGE
.   Data base management system extending structure
.   Stroke typing system
.   Electronic dictionary
.   Parser for natural language text
.   Symbolic language data processing system
.   Speech synchronized animation
.   Remote language translating device
.   Method of operating a computer system to provide customed I/O
        information including language translation
.   Collocational grammar system
.   System of encoding chinese characters according to their patterns
    and accompanying keyboard for electronic computer
.   Multiple language telephone answering machine
.   Interactive speech recognition apparatus
.   Method of using a created international language as an intermediate
        pathway in translation between two national languages
.   Translation system allowing user designation of postpositional words
.   Shorthand notation and transcribing method

LEARNING
.   N-dimensional coulomb neural network which provides for cumulative
        learning of internal representations
.   Optimum fast textural feature extractor
.   Air/fuel mixture ratio control system for internal combustion engine
        with feature of learning correction coefficient including altitude
        dependent factor
.   Autonomous resource management system with recorded evaluations of
        system performance with scheduler control including knowledge
        learning function
.   Character reading method
.   Neural network system for adaptive sensory-motor coordination of
        multijoint robots for single postures
.   Electronic learning control apparatus for internal combustion engine
.   Electronically-controlled, adaptive automatic transmission system
.   Neuromorphic learning networks
.   Electronic air-fuel ratio control apparatus in internal combustion engine
.   Air-fuel ratio control system for an automotive engine
.   Fuel injection system of an internal combustion engine
.   Method of controlling fuel in an engine
.   Engine idling speed controlling system

NEURAL NETWORKS
.   N-dimensional coulomb neural network which provides for cumulative
        learning of internal representations
.   Solitary wave circuit for neural network emulation
.   Spike transmission for neural networks
.   Parallel neural network for a full binary adder
.   Digital adaptive receiver employing maximum-likelihood sequence
        estimation with neural networks
.   Neural network system for adaptive sensory-motor coordination of
        multijoint robots for single postures
.   Devices for neural signal transmission
.   Neural network model in pattern recognition using probabilistic
        contextual information
.   Neural networks
.   Programmable ferroelectric polymer neural network
.   Switched neural networks
.   Neural network with dynamic refresh capability

PATTERN RECOGNITION
.   Radar detection of hazardous small scale weather disturbances
.   Method and apparatus for tracking, mapping and recognition of
        spatial patterns
.   Pattern recognition apparatus using oscillating memory circuits
.   Character reading method
.   System for continuous speech recognition through transition networks
.   Communications network routing and management system
.   Speech recognition system which avoids ambiguity when matching
        frequency spectra by employing an additional verbal feature
.   Speech recognition system
.   Pattern recognizing device
.   Optical character reader with skew recognition
.   Neural network model in pattern recognition using probabilistic
        contextual information
.   Error detection circuit
.   Apparatus and method for recognizing speech
.   Pattern recognition method
.   Voice recognizing telephone
.   Speech recognition arrangement with preselection
.   Image recognition audience measurement system and method

ROBOTICS
.   Rotary to linear motion robot arm
.   Automated phasing device for phasing wheel attachment bolts and methods
        utilizing same
.   Electric control apparatus for industrial robot
.   Nuclear fuel pellet collating system and method
.   Method for positioning a robotic work system
.   Robot vision cooling/protection system
.   Industrial playback robot having a teaching mode
.   Robot for tire building machine and method of operation
.   Industrial robot
.   Velocity control apparatus
.   Deburring robot
.   Digital robot control having an improved pulse width modulator
.   Deadbeat control of disk drive actuator
.   Method for positioning a tool of a multi-joint robot
.   Parallel gripper
.   Apparatus for mastering a robot
.   Industrial laser robot system
.   Welding system for hollow thin walled members
.   Distributed proximity sensor system having embedded light emitters
        and detectors
.   Movable accomodation or container in which is arranged apparatus
        for automatic milking of an animal
.   Robotic product server and system
.   Robotic system
.   Fluid distribution to multiple users through distributed
        intelligence sub-centers
.   Object collision detection method and apparatus
.   Control system for an industrial robot
.   Apparatus and method for mounting window glasses on automobile
.   Polishing robot and polishing method using the same
.   Failsafe brake for a multi-wheel vehicle with motor controlled steering
.   Industrial robot control device
.   Portable robot with automatic set-up
.   Method for controlling operation of industrial robot
.   Visual navigation system for a mobile robot having capabilities
        of regenerating of hidden images
.   Variable compliance device
.   Robot positioner and seal arrangement for a closed chamber
.   Melt indexer system with robot operation
.   Automatic tool changer for workpiece processing machines
.   Locus interpolation device
.   Neural network system for adaptive sensory-motor coordination of
        multijoint robots for single postures
.   Paint-coating brush
.   Vehicle automatic fueling assembly
.   Apparatus for inspecting wafers
.   Robot system for forming a structural component of a preimpreganted
        fiber reinforced tape
.   Three-dimensional measuring robot
.   Robot arm with an assembly flange for tools
.   Wafer centration device
.   Stepping motor control
.   Ultrasonic scanning system
.   Dextrous spherical robot wrist
.   Robot gripper passively locked
.   Method for determining points in space guiding the movement of a robot arm
.   Three-dimensional position sensor and three-dimensional position
        setting system
.   Method and apparatus for assembling an instrument panel in an automobile
.   Apparatus for dealing with cables in industrial robots
.   Method for assembling associated components
.   Novel automatic tool changer
.   Robot apparatus
.   Position and velocity feedback system for a digital robot control
.   Circuit location sensor for component placement apparatus
.   Vision system for distinguishing touching parts
.   Manipulator with rod mechanism
.   Digital robot control providing pulse width modulation for a
        brushless DC drive
.   Magnetically levitated fine motion robot wrist with programmable
        compliance
.   Locomotion-command method for mobile robots
.   Apparatus for installing bearings on engine components
.   Support for a gripper for an industrial robot
.   Robot control apparatus for controlling a manipulator through a
        robot arm having a plurality of axes
.   Device for forecasting breakage cables in an industrial robot
.   Method and apparatus for reconstructing three-dimensional surfaces
        from two-dimensional images
.   Drill inspection and sorting method and apparatus
.   Method and apparatus for applying sealing material to automotive
        vehicle bodies
.   Laser beam robot for cutting and welding
.   Method and apparatus for controlling a welding robot forming a
        nonuniform weld satisfying predetermined criteria related to
        an interspace between elements being welded
.   Water jet trim head simulator
.   Coupling method and apparatus for use with robotic devices and the like
.   Communication interface for multi-microprocessor servo control in
        a multi-axis robot control system
.   Industrial robot device including a robot and a processing machine
.   Multiprocessor position/velocity servo control for multiaxis
        digital robot control system
.   Apparatus for cleaning a textile machine comprising a plurality
        of operating positions
.   Robot articulation joint
.   Gripper head
.   Industrial robot adjustment device
.   Gas laser device
.   Equipment for automatic personalizing of credit cards
.   Drilling derrick device
.   Support for a gripper
.   Multiprocessor torque servo control for multiaxis digital robot
        control system
.   Method for coordinated control of motion devices
.   Multiaxis robot control having improved energy monitoring system
        for protecting robots against joint motor overload
.   Display unit for controlling pattern printing
.   Automated cartridge system
.   Lifting hand for a punch press tool changer
.   Passive actuator to maintain a constant normal cutting force during
        robotic deburring
.   Clutch for robot or like
.   Offset mechanical gripper
.   Method and apparatus for the injection molding of circuit boards
.   Resistance spot welding gun and transformer assembly
.   Sonic positioning device
.   Arm structure for an industrial robot
.   Overload protector for a robot arm
.   Method and apparatus for adaptive force and position control of
        manipulators
.   Robotic hand with shape determination capabilities
.   Robotic workcell control system having improved input/output
    interfacing for better workcell operation
.   Robotic vision system
.   Robotic ultrasonic cleaning and spraying device for ships' hulls
.   Riveting process and apparatus
.   Method and system for loading wafers
.   Robotic accessible wafer shipper assembly
.   Gripper device
.   Dual port alignment assembly station for attaching components to
        circuit boards
.   Robotic airbrush apparatus
.   Robotic crawling device
.   Mechanical fingers for dexterity and grasping
.   Wrist mechanism for robotic manipulations
.   Robotic pipe crawling device
.   Double-ended termination and routing arrangement for an automated
        wiring system
.   Water cooled semi-automatic welding gun
.   Article vending machine employing unique robotic arm and the
        robotic arms employed therein
.   Robotic gripper head
.   Gripping device
.   Sealant flow control for robotic applications

RULE BASED SYSTEMS
.   Speech synthesis system by rule using phonemes as systhesis units
.   System and method for preprocessing and transmitting echo waveform
        information
.   Coalescing changes in pattern-directed, rule-based artificial
        intelligence production systems
.   Diagnostic configuration management for a data processing system
.   Computer speech system
.   Using infrared imaging to monitor and control welding
.   Fiber optic solder joint inspection system
.   Document processing system deciding apparatus provided with
        selection functions
.   Method of starting thermal power plant
.   Automated production dispatch system with feedback control
.   Domain independent shell for building a diagnostic expert system
.   Processing method and processor for machine translation
.   Auto-tuning controller using fuzzy reasoning to obtain optimum
        control parameters
.   Speech synthesis system of rule-synthesis type
.   Reasoning system for reasoning with uncertainty

SPEECH RECOGNITION AND GENERATION
.   Digital speech interpolation system and speech detector
.   Noise compensation in speech recognition apparatus
.   Industrial playback robot having a teaching mode in which teaching
        data are given by speech
.   Method and apparatus of rejecting false hypotheses in automatic
        speech recognizer systems
.   Speech synthesis system by rule using phonemes as systhesis units
.   Digital speech coder having improved vector excitation source
.   Automatic validation of telephone account numbers
.   Speech coding transmission equipment
.   Voice synthesis utilizing multi-level filter excitation
.   Computer speech system
.   System for continuous speech recognition through transition networks
.   Speech synchronized animation
.   Processing of acoustic waveforms
.   Apparatus for speech recognition
.   Synthesized speech-facilitated product
.   Speech recognition system which avoids ambiguity when matching
        frequency spectra by employing an additional verbal feature
.   Speech recognition system
.   Method for extracting formant frequencies
.   Synthesizing word baseforms used in speech recognition
.   Speech recognition system
.   Parallel processing pitch detector
.   Speech recognition system
.   Speech recognition system with an accurate recognition function
.   ASCII LPC-10 conversion
.   Method for entering digit sequences by voice command
.   Vector excitation speech or audio coder for transmission or storage
.   Sub-band speech analyzing and synthesizing device
.   Apparatus and method for recognizing speech
.   Apparatus for extracting features from a speech signal
.   Interactive speech recognition apparatus
.   Method for performing time-scale modification of speech information
        or speech signals
.   Method of recognizing a control command in a system, and interactive
        system for carrying out the method
.   Speech synthesis system of rule-synthesis type
.   Binary autocorrelation processor
.   Speech recognition arrangement with preselection
.   Method of evaluating speech

THEOREM PROVING
.   Digital circuit design verification

VISION
.   Robot vision cooling/protection system
.   Robotic vision system
.   Computer vision system with improved object orientation technique
.   Machine vision system for position sensing
.   Method and apparatus for automatically inspecting and classifying
        different objects
.   Method and apparatus for the perception of computer-generated imagery
.   Method and apparatus for differentiating a planar textured surface
        from a surrounding background
.   Vision system for distinguishing touching parts
.   Workstation for a vision-impaired user with interface for selectively
        feeding display data from a bus or a connected computer
.   Dual port alignment assembly station for attaching components to
        circuit boards
.   Machine vision process and apparatus for reading a plurality of
        separated figures

===========================================================================

