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

complexity classesfinite modelsfinite variable logicsfixpoint logicssurvey

Mathematics Subject Classification ID

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

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

(13)

• Bounded variable logics: Two, three, and more
• Three-variable statements of set-pairing
• How many first-order variables are needed on finite ordered structures?
• scientific article; zbMATH DE number 446838 (Why is no real title available?)
• Some connections between finite and infinite model theory
• Model theoretic methods for fragments of FO and special classes of (finite) structures
• On a theorem of Vaught for first order logic with finitely many variables
• scientific article; zbMATH DE number 408792 (Why is no real title available?)
• Finite Variable Logics in Descriptive Complexity Theory
• scientific article; zbMATH DE number 1136099 (Why is no real title available?)
• Provability with Finitely Many Variables
• Transposition of variables is hard to axiomatize
• Linear algebraic quantifiers

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)