Game-based notions of locality over finite models

Simple item page
dc.contributor.authorArenas, Marcelo
dc.contributor.authorBarceló, Pablo
dc.contributor.authorLibkin, Leonid
dc.date.accessioned2024-01-10T14:22:39Z
dc.date.available2024-01-10T14:22:39Z
dc.date.issued2008
dc.description.abstractLocality 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. (c) 2007 Elsevier B.V. All rights reserved.
dc.description.funderEngineering and Physical Sciences Research Council
dc.fechaingreso.objetodigital19-04-2024
dc.fuente.origenWOS
dc.identifier.doi10.1016/j.apal.2007.11.012
dc.identifier.issn0168-0072
dc.identifier.urihttps://doi.org/10.1016/j.apal.2007.11.012
dc.identifier.urihttps://repositorio.uc.cl/handle/11534/79978
dc.identifier.wosidWOS:000254378600002
dc.information.autorucEscuela de ingeniería ; Arenas, Marcelo ; 0000-0003-3678-1868 ; 81488
dc.issue.numero1-3
dc.language.isoen
dc.nota.accesocontenido parcial
dc.pagina.final30
dc.pagina.inicio3
dc.revistaAnnals of Pure and Applied Logic
dc.rightsacceso restringido
dc.subjectFinite model theory
dc.subjectGaifman locality
dc.subjectHanf locality
dc.subjectGames
dc.subjectUNARY QUANTIFIERS
dc.subjectTHEOREM
dc.subjectLOGICS
dc.titleGame-based notions of locality over finite models
dc.typeartículo
dc.volumen152
sipa.codpersvinculados81488
sipa.indexWOS
sipa.trazabilidadCarga SIPA;09-01-2024
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
2024-04-17. Game-based notions of locality over finite models.pdf
Size:
2.77 KB
Format:
Adobe Portable Document Format
Description:
Download
Collections
Artículos de revistas