An incremental update algorithm modifies the solution of a problem that has been changed, rather than re-solving the entire problem. ACINCF and ACINCB are incremental update algorithms for forward and backward data-flow analysis, respectively, based on our equations model of Allen-Cocke interval analysis. In addition, we have studied their performance on a “nontoy” structured programming language L. Given a set of localized program changes in a program written in L, we identify a priori the nodes in its flow graph whose corresponding data-flow equations may be affected by the changes. We characterize these possibly affected nodes by their corresponding program structures and their relation to the original change sites, and do so without actually performing the incremental updates . Our results can be refined to characterize the reduced equations possibly affected if structured loop exit mechanisms are used, either singly or together, thereby relating richness of programming language usage to the ease of incremental updating.

A procedure is described for minimizing the number of states in an asynchronous sequential function when the restriction exists that the input cannot change while the sequential function is in an unstable state. Furthermore, a procedure is described for minimizing the number of states in a sequential function when the restriction also exists that each output can change at most once during the time required for a transition from one stable state to another.

Given a sequential switching function in the form of a flow table in which some of the entries are unspecified, the problem of reducing the number of rows in that flow table is extremely complex, and cannot, in general, be solved by any simple extension of the methods used for completely specified functions. An analysis of the problem is presented, and a partially enumerative solution is evolved. A rough indication of the efficiency of the given procedures may be obtained from the fact that these techniques have been successfully applied to approximately two dozen tables ranging up to about 15 rows. No solution required more than two hours.