Finite Variable Logics in Descriptive Complexity Theory
DOI10.2307/420954zbMath0940.03040OpenAlexW2009700100MaRDI QIDQ4254565
Publication date: 29 June 1999
Published in: Bulletin of Symbolic Logic (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/516ed34d23a6639367393f67be21c9b312b2db07
surveyfinite modelscanonical modelsfinite variable logicscomplexity of equivalence testingfinite variable theories
Complexity of computation (including implicit computational complexity) (03D15) Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19) Inductive definability (03D70)
Related Items (5)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fixed-point extensions of first-order logic
- Upper and lower bounds for first order expressibility
- An analysis of fixed-point queries on binary trees
- Infinitary logics and 0-1 laws
- An optimal lower bound on the number of variables for graph identification
- How to define a linear order on finite models
- Computer science logic. 11th international workshop, CSL '97. Annual conference of the EACSL, Aarhus, Denmark, August 23--29, 1997. Proceedings
- Logical hierarchies in PTIME
- Definability hierarchies of generalized quantifiers
- Structure and complexity of relational queries
- Infinitary logic and inductive definability over finite structures
- Almost Everywhere Equivalence of Logics in Finite Model Theory
- A zero-one law for logic with a fixed-point operator
- Relational queries computable in polynomial time
- Languages that Capture Complexity Classes
- Random Graph Isomorphism
- On the Decision Problem for Two-Variable First-Order Logic
- Fixpoint logics, relational machines, and computational complexity
- Generalized Quantifiers and Logical Reducibilities
This page was built for publication: Finite Variable Logics in Descriptive Complexity Theory
