In this paper an algebraic characterization of the class DLIN of functions that can be computed in linear time by a deterministic RAM using only numbers of linear size is given. This class was introduced by grandjean, who showed that it is robust and contains most computational problems that are usually considered to be solvale in deterministic linear time. The characterization is in terms of a recursion scheme for unary functions. A variation of this recursion scheme characterizes DLINEAR, the class which allows polynomially large numbers. A second variation defines a class that still contains DTIME(n), the class of funcitons that are From these algebraic characterizations, logical characterizations of DLIN and DLINEAR as well as complete problems (under DTIME(n) reductions) are derived.
展开▼
