Complexity of algebraic implementations for abstract data types

摘要

A notion of complexity for algebraic implementations of abstract data types is introduced and studied. The main results concern the expressive power of algebraic specifications and implementations as well as upper and lower bounds on the complexity of implementations in terms of time on Turing Machines.