scientific article; zbMATH DE number 1302669

zbMATH Open0936.03032MaRDI QIDQ4249221FDOQ4249221

Authors: Anuj Dawar 

Publication date: 17 May 2000

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

Title of this publication is not available (Why is that?)

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?

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)

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?
• Title not available (Why is that?)
• Title not available (Why is that?)

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)