D. D. Sleator, Data Structures and Cost-bounded Petri Nets , Carnegie Mellon University, Computer Science, 1992

Consider a collection of particles of various types, and a set of reactions that are allowed to take place among these particles. Each reaction is defined by an input linear combination of particles, and an output linear combination of particles. This framework (which is a Petri net) is shown to model the cost of updating several standard data structures, the amortized cost of counting in various number systems and the space consumption of persistent data structures. A proof that the system of reactions is guaranteed to terminate gives a bound on the cost of the corresponding data structure problem. I show how linear programming can be used to analyze these systems.

Daniel Sleator: Email, Home Page, Papers

Last modified: Sat Jan 21 07:15:44 EST 2006