Number of variables is equivalent to space

DOI10.2307/2695103MaRDI QIDQ2758055zbMATH OpenOpenAlexFDO

Authors Jonathan F. Buss, David A. Mix Barrington, Neil Immerman

Publication date 6 December 2001

Published in The 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)

Recommendations

• Finite Variable Logics in Descriptive Complexity Theory
• Complexity Results for First-Order Two-Variable Logic with Counting
• Definability with bounded number of bound variables
• scientific article; zbMATH DE number 408792
• scientific article; zbMATH DE number 1086662

Cites work

• scientific article; zbMATH DE number 1302020 (Why is no real title available?)
• Expressibility and Parallel Complexity
• Languages that Capture Complexity Classes
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• On uniformity within \(NC^ 1\)
• Relational queries computable in polynomial time
• Structure and complexity of relational queries
• Upper and lower bounds for first order expressibility

Cited in

(4)

• How many variables are needed to express an existential positive query?
• How many variables are needed to express an existential positive query?
• A CHARACTERIZATION OF THE ARITHMETICAL HIERARCHY BY LANGUAGE EQUATIONS
• Ehrenfeucht-Fraïssé Games on Random Structures

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2758055)