Rudimentary reductions revisited

Journal article

Peer reviewed

Rudimentary reductions revisited

Eric Allender and Vivek Gore

Information processing letters, Vol.40(2), pp.89-95

1991

DOI: https://doi.org/10.1016/0020-0190(91)90015-A

Abstract

theory of computation

Computational complexity

formal languages

We show that log-bounded rudimentary reductions (defined and studied by Jones in 1975) characterize Dlogtime-uniform AC 0.

Metrics

11 Record Views

9 Times Cited - Web of Science

See more details

Details

Title: Rudimentary reductions revisited
Creators: Eric Allender
Vivek Gore
Publication Details: Information processing letters, Vol.40(2), pp.89-95
Date published: 1991
Publisher: Elsevier B.V
Academic Unit: Computer Science (SAS)
Language: English
Resource Type: Journal article
Identifiers: 991031654680804646