scientific article; zbMATH DE number 1302669
Model theory of finite structures (03C13) Other infinitary logic (03C75) Complexity of computation (including implicit computational complexity) (03D15) Inductive definability (03D70) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)
Finite variable logics are the fragments of first-order logic or of infinitary logic in which the only variables allowed are \(x_1,\dots,x_k\) for some fixed \(k\geq 1\). This paper surveys a number of results that have been established for finite variable logics, from purely model-theoretic ones to results concerning computational complexity classes. ``By focusing on the common techniques, this survey aims to expose the underlying connections between a variety of investigations. For the entire collection see [Zbl 0913.00019].
- Bounded variable logics: Two, three, and more
- Three-variable statements of set-pairing
- How many first-order variables are needed on finite ordered structures?
- scientific article; zbMATH DE number 446838 (Why is no real title available?)
- Some connections between finite and infinite model theory
- Model theoretic methods for fragments of FO and special classes of (finite) structures
- On a theorem of Vaught for first order logic with finitely many variables
- scientific article; zbMATH DE number 408792 (Why is no real title available?)
- Finite Variable Logics in Descriptive Complexity Theory
- Types and indiscernibles in finite models
- Provability with Finitely Many Variables
- Transposition of variables is hard to axiomatize
- Linear algebraic quantifiers
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4249221)
