Finite Variable Logics in Descriptive Complexity Theory
DOI10.2307/420954zbMATH Open0940.03040OpenAlexW2009700100MaRDI QIDQ4254565FDOQ4254565
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
Recommendations
surveycanonical modelsfinite modelsfinite variable logicscomplexity of equivalence testingfinite variable theories
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)
Cites Work
- Title not available (Why is that?)
- Fixed-point extensions of first-order logic
- Random Graph Isomorphism
- Languages that Capture Complexity Classes
- Title not available (Why is that?)
- On the Decision Problem for Two-Variable First-Order Logic
- An optimal lower bound on the number of variables for graph identification
- Almost Everywhere Equivalence of Logics in Finite Model Theory
- Relational queries computable in polynomial time
- Definability hierarchies of generalized quantifiers
- Generalized Quantifiers and Logical Reducibilities
- Computer science logic. 11th international workshop, CSL '97. Annual conference of the EACSL, Aarhus, Denmark, August 23--29, 1997. Proceedings
- Upper and lower bounds for first order expressibility
- Title not available (Why is that?)
- Structure and complexity of relational queries
- A zero-one law for logic with a fixed-point operator
- Infinitary logic and inductive definability over finite structures
- Infinitary logics and 0-1 laws
- Logical hierarchies in PTIME
- Fixpoint logics, relational machines, and computational complexity
- How to define a linear order on finite models
- An analysis of fixed-point queries on binary trees
Cited In (14)
- Title not available (Why is that?)
- 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
- Title not available (Why is that?)
- 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
- Title not available (Why is that?)
- Title not available (Why is that?)
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)
