Model theory of tame classes of finite structures II
Anuj Dawar
Chair: Johanna Franklin
The class of finite structures is a notoriously ill-behaved one from the point of view of model theory. In the early years of this century, this led to the study of subclasses of this class which exhibit better behaviour. The focus was on classes defined by the sparsity of their underlying Gaifman graph. Such sparse classes were shown to be well-behaved in model-theoretic and algorithmic terms. A review of the work on this, as of 2007 can be found in [1]. The good behaviour discussed there focussed on two aspects: that such classes show preservation properties that fail on the class of finite structures, and evaluation of first-order formulas is algorithmically tractable in such classes. A common theme is the use of the locality of first-order logic which, in the absence of compactness, is a key tool of finite model theory. The line of work on the algorithmic evaluation of first-order formulas in sparse classes culminated in the result of Grohe et al. on nowhere-dense classes of structures [2]. More recent work has sought to extend this work to classes of finite structures that are not sparse, and identify tame classes of dense structures. This has seen a convergence with notions of tameness coming from stability theory (see, for example, [3]).
In this tutorial, I review the the use of locality in identifying tame classes; discuss the tameness of some sparse classes; and present some recent extensions to dense classes and the connections with stability. I prove the results for illustrative examples of classes.
Bibliography
- A. Dawar,Finite model theory on tame classes of structures,Intl. Symp. on Mathematical Foundations of Computer Science,Springer LNCS,(2007**,pp. 2–12.
- M. Grohe, S. Siebertz, S. Kreutzer_Deciding first-order properties of nowhere dense graphs_,Journal of the ACM, vol. 64 (2017**, no. 3, pp. 17:1–17:32
- S. Braunfeld, A. Dawar, I. Eleftheriadis, A. Papadopoulos_Monadic NIP in monotone classes of relational structures_,Intl. Colloq. Automata, Languages, and Programming,LIPCs(2023),pp. 119:1–119:18.