In this paper we show that nondeterministic space s(n) is closed under complementation for
s(n) greater than or equal to \logn. It immediately follows that the context-sensitive …

Algebraic complexity theory | Annual review of computer science: vol. 3, 1988 skip to main
content ACM Digital Library home ACM home Google, Inc. (search) Advanced Search Browse …

Recently a new connection was discovered between the parallel complexity class NC 1 and
the theory of finite automata in the work of Barrington on bounded width branching …

We consider the parallel time complexity of logic programs without function symbols, called
logical query programs, or Datalog programs. We give a PRAM algorithm for computing the …

A formal algebraic model for divide-and-conquer algorithms is presented. The model reveals
the internal structure of divide-and-conquer functions, leads to high-level and functional …

We survey the many applications of parallel algorithms and complexity to logic programming
problems. The problems examined are related to the optimization of logical query programs …

We obtain a characterization of strings in D 2 (the one-sided Dyck language over two letters)
and use this characterization to show that D 2 is in NC 1 (under ALOGTIME reductions). Our …

Modular integer exponentiation (given a, e, and m, compute ae mod m) is a fundamental
problem in algebraic complexity for which no efficient parallel algorithm is known. Two …

Currently, there is a great deal of excitement about research in the area of parallel
algorithms. Considerable progress has been made in many areas: graph theory …

We design a fast parallel algorithm for determining all maximal cliques (maximal
independent sets) in an arbitrary graph, working in O (log 3 (nM)) parallel time and O (M 6 n …