This paper discusses how to extend a “dictionary machine” which handles only (known to be) nonredundant sequences of modifications to a dictionary to one that recognizes and eliminates redundant operations from a sequence of dictionary operations. If the simpler machine has n processors and it processes a nonredundant sequence in time T(n) with period P(n), then by adding Order(T(n)) extra processors the machine will recognize and eliminate redundancies in the sequence in time 3T(n) + Order(1) with period 2P(n). A second result asserts that a dictionary machine existing with n storage processors can process any sequence of redundant operations over the set S in time T(n) = Order(log(n)) and with period P(n) = Order(1) if the cardinality of S is not greater than n. Both results are proved as theorems.

I found the paper interesting, although it could be a bit clearer. “Systolic” is not defined, but it should be. It took me a while to realize what the author means by “redundant” and “non-redundant.”