A constant-space sequential model of computation for first-order logic (Q1271562)

A natural sequential model of computation with a constant amount of read/write work space, despite unlimited (polynomial) access to read-only output, is defined. The model is deterministic, uniform, and sequential. The constant work space is modeled by a finite number of destructively read Boolean variables, assignable by formulas over the canonical Boolean operations. It is shown that computation on this model is equivalent to expressibility in first-order logic, giving a duality between (read-once) constant-space serial algorithms and constant-time parallel algorithms.