ZDD
Structures and Families of Sets Donald E. Knuth |
|||

ABSTRACT Information is represented inside a computer by using structures that mimic mathematical models. Many different kinds of models can be used for the same information; conversely, many different kinds of information can be represented with the same model. One of the main reasons that we are able to solve problems efficiently is that we have mathematical tools that tell us how to convert between alternative representations.
This talk focuses on one of the most fundamental mathematical
models, the notion of a A family of sets is naturally represented by a data structure called a ZDD. Two or more families are combined by basic operations such as union, intersection, join, meet, quotient. We are often interested in, say, the maximal sets of a family, or in the members of one family that don't contain any members of another, etc. Such operations form a "family algebra," and there are interesting algorithms to implement the operations of family algebra as operations on ZDDs. Family algebra is a relatively new topic that is just beginning to be understood. Examples will be given of applications to (i) families of words in a dictionary; (ii) families of patterns that tile a shape; (iii) families of cycles and paths in a graph or network. Bio He is a member of the American Academy of Arts and Sciences, the National Academy of Sciences, and the National Academy of Engineering, and he is a foreign associate of the French, Norwegian, Bavarian, and Russian science academies as well as the Royal Society of London. He received the Turing Award from the Association for Computing Machinery in 1974; the National Medal of Science from President Carter in 1979; the Steele Prize from the American Mathematical Society in 1986; the Adelsköld Medal from the Royal Swedish Academy of Sciences in 1994; the Harvey Prize from the Technion of Israel in 1995; the John von Neumann Medal from the Institute of Electrical and Electronic Engineers in 1995; and the Kyoto Prize from the Inamori Foundation in 1996. He holds honorary doctorates from Oxford University, the University of Paris, the Royal Institute of Technology in Stockholm, the University of St. Petersburg, the University of Marne-la-Vallée, Masaryk University, St. Andrews University, Athens University of Economics and Business, the University of Macedonia in Thessaloniki, the University of Tübingen, the University of Oslo, the University of Antwerp, the Swiss Federal Institute of Technology in Zürich, the University of Bordeaux, and nineteen colleges and universities in America. More information about Donald E. Knuth. |