Elements of Finite Model Theory

By Leonid Libkin. Texts in Theoretical Computer Science, 2004

1,088 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Descriptive Complexity, Canonisation, and Definable Graph Structure Theory (2017, background): “For a thorough introduction to the topic, see [6, 10, 18, 21].”
TriAL (2018, background): “Since FO 6 is contained in L 6 ∞ , ω (see, e.g., Reference [36]), all the base cases except the star follow from the first part of Proposition 4.5, and so we only need to show how recursion is handled.”
Foundations of JSON Schema (2016, background): “Because of this we next show that JSON Schema documents can be expressed in monadic second order logic (MSO), a powerful logical formalism often used to cover languages containing some form of regular expressions [21].”
Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement (2013, neutral): “yE(x,y))))). This formula is not equivalent to any formula of L2. Two-variable logics, and more generally ﬁnite variable logics, have been studied extensively in ﬁnite model theory (see, for example, [11,15,18,13]). We call two vertices of a graph L2-equivalent (C2-equivalent) if they satisfy the sa”