Game-based notions of locality over finite models

Arenasa, M; Barceló P.; Libkin, L

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 neighbourhood of its free variables. Such notions have proved to be useful in many applications. They all, however, refer to isomorphisms of neighbourhoods, which most local logics cannot test. A stronger notion of locality says that the truth value of a formula is determined by what the logic itself can say about that small neighbourhood. Since the expressiveness of many logics can be characterized by games, one can also say that the truth value of a formula is determined by the type, with respect to a game, of that small neighbourhood. Such game-based notions of locality can often be applied when traditional isomorphism-based notions of locality cannot. Our goal is to study game-based notions of locality. We work with an abstract view of games that subsumes games for many logics. We look at three, progressively more complicated locality notions. The easiest requires only very mild conditions on the game and works for most logics of interest. The other notions, based on Hanf's and Gaifman's theorems, require more restrictions. We state those restrictions and give examples of logics that satisfy and fail the respective game-based notions of locality. © 2007 Elsevier B.V. All rights reserved.

Más información

Título según WOS: Game-based notions of locality over finite models
Título según SCOPUS: Game-based notions of locality over finite models
Título de la Revista: ANNALS OF PURE AND APPLIED LOGIC
Volumen: 152
Número: 01-mar
Editorial: ELSEVIER SCIENCE BV
Fecha de publicación: 2008
Página de inicio: 3
Página final: 30
Idioma: English
URL: http://linkinghub.elsevier.com/retrieve/pii/S0168007207001054
DOI:

10.1016/j.apal.2007.11.012

Notas: ISI, SCOPUS