Finite Variable Logics in Descriptive Complexity Theory
From MaRDI portal
Publication:4254565
DOI10.2307/420954zbMath0940.03040MaRDI 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
survey; finite models; canonical models; finite variable logics; complexity of equivalence testing; finite variable theories
03D15: Complexity of computation (including implicit computational complexity)
03C13: Model theory of finite structures
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q19: Descriptive complexity and finite models
03D70: Inductive definability
Related Items
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
