Number of variables is equivalent to space

DOI10.2307/2695103zbMath0986.68040OpenAlexW2149642761MaRDI QIDQ2758055

Jonathan F. Buss, David A. Mix Barrington

Publication date: 6 December 2001

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/2695103

zbMATH Keywords

descriptive complexity

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Descriptive complexity and finite models (68Q19)

Related Items (2)

A CHARACTERIZATION OF THE ARITHMETICAL HIERARCHY BY LANGUAGE EQUATIONS ⋮ Ehrenfeucht-Fraïssé Games on Random Structures

Cites Work

• Unnamed Item
• Upper and lower bounds for first order expressibility
• Structure and complexity of relational queries
• On uniformity within \(NC^ 1\)
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• Relational queries computable in polynomial time
• Languages that Capture Complexity Classes
• Expressibility and Parallel Complexity

This page was built for publication: Number of variables is equivalent to space