A constant-space sequential model of computation for first-order logic (Q1271562)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: A constant-space sequential model of computation for first-order logic |
scientific article; zbMATH DE number 1220921
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A constant-space sequential model of computation for first-order logic |
scientific article; zbMATH DE number 1220921 |
Statements
A constant-space sequential model of computation for first-order logic (English)
0 references
10 November 1998
0 references
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.
0 references
descriptive complexity theory
0 references
sequential model of computation
0 references
constant work space
0 references
expressibility in first-order logic
0 references
constant-space serial algorithms
0 references
constant-time parallel algorithms
0 references
0 references
0.98313564
0 references
0.87476486
0 references
0.8724816
0 references
0.87086666
0 references
0.8681606
0 references
0.86774886
0 references
0.86544853
0 references
