6533b823fe1ef96bd127defe

RESEARCH PRODUCT

Algebraic and logical characterizations of deterministic linear time classes

Thomas Schwentick

subject

AlgebraClass (set theory)Turing machinesymbols.namesakeGlobal functionsymbolsComputational problemBinary stringsAlgebraic numberCharacterization (mathematics)Time complexityMathematics

description

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 solvable in deterministic linear time.

yearjournalcountryeditionlanguage
1997-01-01
https://doi.org/10.1007/bfb0023481