Abstract

Locality notions in logic say that the truth value of a formula can be determined locally, by looking at the isomorphism type of a small neighborhood of its free variables. Such notions have proved to be useful in many applications especially in computer science. They all, however, refer to isomorphism of neighborhoods, which most local logics cannot test. A more relaxed notion of locality says that the truth value of a formula is determined by what the logic itself can say about that small neighborhood. Or, since most logics are characterized by games, the truth value of a formula is determined by the type, with respect to a game, of that small neighborhood. Such game-based notions of locality can often be applied when traditional isomorphism-based locality cannot. In the first part of this talk, we show some recent results on game-based notions of locality. We look at two, progressively more complicated locality notions, and we show that the overall picture is much more complicated than in the case of isomorphism-based notions of locality. In the second part of this talk, we concentrate on the locality of transformations, rather than queries definable by formulas. In particular, we show how the game-based notions of locality can be used in data exchange settings to prove inexpressibility results. © 2006 International Federation for Information Processing.