Speaker
Anuj Dawar
University of Cambridge
Talks at this conference:
| Monday, 10:00, J222 |
Model theory of tame classes of finite structures I |
|
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
|
|
| Monday, 11:30, J222 |
Model theory of tame classes of finite structures II |
|
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
|
|
| Tuesday, 10:00, J222 |
Model theory of tame classes of finite structures III |
|
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
|