Elements of Finite Model Theory¶
Libkin, L. (2004). Elements of Finite Model Theory. Springer.
Cited by¶
2 citations across 1 artifact.
Each citation links to the sentence it supports in the citing article.
Domain-specific¶
- Quantifier Rank
- Leonid Libkin uses this definition to form the bounded fragment \(\mathrm{FO}[k]\) of first-order formulas whose rank is at most \(k\).
This sourceDefines quantifier rank and \(\mathrm{FO}[k]\), distinguishes it from total quantifier count and prenex count, and connects rank to Ehrenfeucht–Fraïssé equivalence.
- For a fixed finite relational vocabulary and fixed tuple of free variables, Libkin proves that only finitely many \(\mathrm{FO}[k]\) formulas exist up to logical equivalence and that rank-\(k\) types can themselves be represented by formulas of rank \(k\).
This sourceEstablishes finiteness up to equivalence and rank-\(k\) type results for fixed finite relational vocabularies and fixed free-variable arity.
- Leonid Libkin uses this definition to form the bounded fragment \(\mathrm{FO}[k]\) of first-order formulas whose rank is at most \(k\).
Verification¶
This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.
Registry ID ref:84c178198e1f · see in the full table