Generalizing finitemodel theory

Michael BenediktCambridge 2017 · DOI · OpenAlex

Abstract

. We overview work on languages for querying finite structures, where the finite structures “live” inside some infinite interpreted structure. The goal is to take the query languages that have been investigated in finite model theory —first-order logic, second-order logic, fixpoint logic, etc. — and find natural extensions of them that take into account the ambient structure. Most of our discussion will be on first-order query languages. From the point of view of model theory, this means we fix an infinite structure and look at first-order formulas with additional relational predicates that range over finite sets; thus our languages lie between first-order logic and weak second order logic. The bulk of the survey consists of characterization theorems stating what sorts of queries can be defined in these logics. Not surprisingly, the expressiveness of first-order queries is determined by the model theory of the infinite structure. When the structure has a decision procedure, one can ask how complex it is to evaluate these formulas, in terms of the size of the finite structure that is plugged in for the free relational parameters. That is, we can consider formulas in these logics as templates for standard formulas, and ask how decision procedures behave as the templates are instantiated differently. The model-theoretic perspective and the symbolic computation perspective turn out to be closely connected. We also discuss applications of the results to spatial databases and to abstract complexity.
BibTeX
@inproceedings{benedikt2017generalizing,
  author = {Michael Benedikt},
  title = {{Generalizing finitemodel theory}},
  booktitle = {Cambridge},
  year = {2017},
  doi = {10.1017/9781316755785.002},
}

Loading related content...

Figure