Complexity of implementations on the level of algebraic specifications
Hartmut Ehrig, Bernd Mahr · 1980
The aim of this paper is to study implementations of abstract data types and their complexity within the framework of algebraic specifications. An implementation of an abstract data type ADTO by an abstract data type ADT1 is defined on a syntactical and on a semantical level where data and operations of ADTO are simulated by those of ADT1. In order to investigate complexity of implemented operations and to compair different implementations we axiomatically introduce complexity measures for the operations in ADTO with respect to a given implementation of ADTO by ADT1. A most natural interesting class of complexity measures which satisfy our axioms is compatible with time complexity of Turing Machines. This is shown by specification and implementation of timebounded Turing Machines within our algebraic framework and the simulation of a general nondeterministic interpreter for algebraic implementations by a nondeterministic Turing Machine. This relationship allows to show the existence of solutions and of upper and lower bounds for the complexity of a broad class of implementation problems in our sense. A corollary shows that there are algebraic specifications for all those recursive functions which are bounded in time by algebraically specifyable functions.