Steven Lindell

Haverford College

A Constant-Space Model of Computation for First-Order Queries

DIMACS Center - Room 431

Busch Campus

Piscataway, New Jersey

November 8, 1995 at **1:00** PM

Abstract:

We present a natural model of computation for constant-space serial algorithms. It differs from the classical finite-state machine in subtle but important ways. Instead of a single head and finite control, the input is accessed using multiple heads with an oblivious control. The actual boolean data calculations are performed separately, and have a read-once restriction imposed upon them. We argue that this approach of measuring read/write work space is more intuitively accurate, and describe it in ordinary terms by a simple deterministic machine with a sequential programming language.

Our model captures first-order logical expressibility, which in the presence of arithmetic is known to coincide with constant-time parallel computability (uniform AC^0). This parallel-time/serial-space duality will be illustrated most beautifully by the example of binary addition, for which our main theorem constructively yields the carry look-ahead algorithm from the bit-serial (elementary school) algorithm. There also appear to be connections between space measurement in this model and quanta of information. This reinforces the notion that first-order logic is a machine-independent query language, and may also give possible insights into space-bounded quantum computation. Extensions to constant-depth threshold circuits (uniform TC^0) and ALOGTIME (uniform NC^1) will also be discussed.