AbstractA study of the general properties of incremental algorithms is presented. First, it is shown that within certain limitations it is not possible for an incremental algorithm to be of complexity less than 11n of that of the best non-incremental algorithm for any given function. Next we describe a model theorem for any given function. Next we describe a model for incremental algorithms based on a generalization of finite state machines. It is demonstrated that all finite state machines have either constant or linear complexity, and this is extended to a subclass of incremental algorithms. Then the requirements for machines with good incremental algorithms or discussed, and two classes are presented, one which can be updated in constant time, and one in V_n time, when averaged over a sequence of changes.
RightsThis Item is protected by copyright and/or related rights.You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use.For other uses you need to obtain permission from the rights-holder(s).