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

DOI10.1007/3-540-60178-3_97MaRDI QIDQ6064294

Steven Lindell

Publication date: 12 December 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

zbMATH Keywords

regular languagedependency graphfinite automatonbinary stringBoolean variable

Mathematics Subject Classification ID

Mathematical logic and foundations (03-XX)

Cites Work

• Unnamed Item
• 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
• Generalized Quantifiers and Logical Reducibilities

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