Finite Variable Logics in Descriptive Complexity Theory
From MaRDI portal
Recommendations
Cites work
- 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
- 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?)
- 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
(20)- A restricted second order logic for finite structures
- Equivalence in finite-variable logics is complete for polynomial time
- Complexity of finite-variable fragments of propositional temporal and modal logics of computation
- A combinatorial characterization of resolution width
- Large finite structures with few \(L^k\)-types
- Number of variables is equivalent to space
- Graphs identified by logics with counting
- How many first-order variables are needed on finite ordered structures?
- scientific article; zbMATH DE number 446838 (Why is no real title available?)
- Semantic restrictions over second-order logic
- scientific article; zbMATH DE number 408792 (Why is no real title available?)
- scientific article; zbMATH DE number 1302669 (Why is no real title available?)
- scientific article; zbMATH DE number 979011 (Why is no real title available?)
- scientific article; zbMATH DE number 1136099 (Why is no real title available?)
- scientific article; zbMATH DE number 1163938 (Why is no real title available?)
- \(\mathrm{FO}=\mathrm{FO}^3\) for linear orders with monotone binary relations
- Complexity and expressivity of propositional dynamic logics with finitely many variables
- First-order definable counting-only queries
- From quantifier depth to quantifier number: separating structures with k variables
- Near-optimal lower bounds on quantifier depth and Weisfeiler-Leman refinement steps
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)
