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

DOI10.1006/inco.1998.2702zbMath0914.03047OpenAlexW2178872860MaRDI QIDQ1271562

Steven Lindell

Publication date: 10 November 1998

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/inco.1998.2702

zbMATH Keywords

descriptive complexity theoryconstant work spaceconstant-space serial algorithmsconstant-time parallel algorithmsexpressibility in first-order logicsequential model of computation

Mathematics Subject Classification ID

Related Items (1)

Multi-head finite automata: Data-independent versus data-dependent computations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Rudimentary reductions revisited
• Regular languages in \(NC\)
• Bounded-width polynomial-size Boolean formulas compute exactly those functions in AC\(^ 0\)
• The complexity of iterated multiplication
• On uniformity within \(NC^ 1\)
• Parity, circuits, and the polynomial-time hierarchy
• Expressibility and Parallel Complexity
• Elementary Properties of the Finite Ranks
• A First-Order Isomorphism Theorem
• Generalized Quantifiers and Logical Reducibilities

This page was built for publication: A constant-space sequential model of computation for first-order logic