Locality of Queries and Transformations

Research output: Contribution to journalArticlepeer-review

Abstract

Locality is a standard notion of finite model theory. There are two well known flavors of it, based on Hanf's and Gaifman's theorems. Essentially they say that structures that locally look alike cannot be distinguished by first-order sentences. Very recently these standard notions have been generalized in two ways. The first extension makes the notion of “looking alike” depend on logical indistinguishability, rather than isomorphism, of local neighborhoods. The second extension considers transformations defined by FO formulae, and requires that small neighborhoods be preserved by those transformations. In this survey we explain these new notions – as well as the standard ones – and show how they behave with respect to Hanf's and Gaifman's conditions.
Original languageEnglish
Pages (from-to)115-127
Number of pages13
JournalElectronic Notes in Theoretical Computer Science
Volume143
DOIs
Publication statusPublished - 2006

Fingerprint Dive into the research topics of 'Locality of Queries and Transformations'. Together they form a unique fingerprint.

Cite this