scientific article; zbMATH DE number 1302669

MaRDI QIDQ4249221zbMATH OpenFDO

Authors Anuj Dawar

Publication date 17 May 2000

Full work available at URL https://eudml.org/doc/208925

zbMATH Keywords

surveycomplexity classesfinite modelsfinite variable logicsfixpoint logics

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19) Other infinitary logic (03C75) Complexity of computation (including implicit computational complexity) (03D15) Inductive definability (03D70)

Recommendations

• scientific article; zbMATH DE number 446838
• Finite Variable Logics in Descriptive Complexity Theory
• How many first-order variables are needed on finite ordered structures?

Cited in

(8)

• Provability with Finitely Many Variables
• On a theorem of Vaught for first order logic with finitely many variables
• Some connections between finite and infinite model theory
• Three-variable statements of set-pairing
• Model theoretic methods for fragments of FO and special classes of (finite) structures
• How many first-order variables are needed on finite ordered structures?
• scientific article; zbMATH DE number 446838 (Why is no real title available?)
• scientific article; zbMATH DE number 408792 (Why is no real title available?)

This page was built for publication:

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