Machine-independent characterizations and complete problems for deterministic linear time

This article presents two algebraic characterizations and two related complete problems for the complexity class DLIN that was introduced in [E. Grandjean, Ann. Math. Artif. Intell., 16 (1996), pp. 183--236]. DLIN is essentially the class of all functions that can be computed in linear time on a Ran...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on computing 2002-01, Vol.32 (1), p.196-230
Main Authors: GRANDJEAN, Etienne, SCHWENTICK, Thomas
Format: Article
Language:English
Subjects:
Algebra
Algorithmics. Computability. Computer arithmetics
Algorithms
Applied sciences
Computer Science
Computer science
control theory
systems
Data Structures and Algorithms
Exact sciences and technology
Graph representations
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This article presents two algebraic characterizations and two related complete problems for the complexity class DLIN that was introduced in [E. Grandjean, Ann. Math. Artif. Intell., 16 (1996), pp. 183--236]. DLIN is essentially the class of all functions that can be computed in linear time on a Random Access Machine which uses only numbers of linear value during its computations. The algebraic characterizations are in terms of recursion schemes that define unary functions. One of these schemes defines several functions simultaneously, while the other one defines only one function. From the algebraic characterizations, we derive two complete problems for DLIN under new, very strict, and machine-independent affine reductions.
ISSN:0097-5397
1095-7111
DOI:10.1137/S0097539799360240