Finite Variable Logics in Descriptive Complexity Theory

DOI10.2307/420954MaRDI QIDQ4254565zbMATH OpenOpenAlexFDO

Authors Martin Grohe

Publication date 29 June 1999

Published in The Bulletin of Symbolic Logic (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/516ed34d23a6639367393f67be21c9b312b2db07, http://www.math.ucla.edu/~asl/bsl/0404-toc.htm

zbMATH Keywords

surveycanonical modelsfinite modelsfinite variable logicscomplexity of equivalence testingfinite variable theories

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) Complexity of computation (including implicit computational complexity) (03D15) Inductive definability (03D70)

Recommendations

• scientific article; zbMATH DE number 1302669
• scientific article; zbMATH DE number 446838
• A restricted second order logic for finite structures
• Equivalence in finite-variable logics is complete for polynomial time

Cites work

• scientific article; zbMATH DE number 1220163 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 686998 (Why is no real title available?)
• A zero-one law for logic with a fixed-point operator
• Almost Everywhere Equivalence of Logics in Finite Model Theory
• An analysis of fixed-point queries on binary trees
• An optimal lower bound on the number of variables for graph identification
• Computer science logic. 11th international workshop, CSL '97. Annual conference of the EACSL, Aarhus, Denmark, August 23--29, 1997. Proceedings
• Definability hierarchies of generalized quantifiers
• Fixed-point extensions of first-order logic
• Fixpoint logics, relational machines, and computational complexity
• Generalized Quantifiers and Logical Reducibilities
• How to define a linear order on finite models
• Infinitary logic and inductive definability over finite structures
• Infinitary logics and 0-1 laws
• Languages that Capture Complexity Classes
• Logical hierarchies in PTIME
• On the Decision Problem for Two-Variable First-Order Logic
• Random Graph Isomorphism
• Relational queries computable in polynomial time
• Structure and complexity of relational queries
• Upper and lower bounds for first order expressibility

Cited in

(14)

• scientific article; zbMATH DE number 7561609 (Why is no real title available?)
• Number of variables is equivalent to space
• First-order definable counting-only queries
• Large finite structures with few \(L^k\)-types
• Graphs identified by logics with counting
• How many first-order variables are needed on finite ordered structures?
• A combinatorial characterization of resolution width
• Complexity and expressivity of propositional dynamic logics with finitely many variables
• scientific article; zbMATH DE number 446838 (Why is no real title available?)
• Complexity of finite-variable fragments of propositional temporal and modal logics of computation
• Equivalence in finite-variable logics is complete for polynomial time
• Semantic restrictions over second-order logic
• scientific article; zbMATH DE number 408792 (Why is no real title available?)
• scientific article; zbMATH DE number 979011 (Why is no real title available?)

This page was built for publication: Finite Variable Logics in Descriptive Complexity Theory

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