ISBN:  Unavailable

Category: Unavailable

Page count: 24

Abstract: "We show that a form of divide and conquer recursion on sets together with the relational algebra expresses exactly the queries over ordered relational databases which are NC-computable. At a finer level, we relate k nested uses of recursion exactly to AC[superscript k], k [> or =] 1. We also give corresponding results for complex objects."