Skip to main content Accessibility help

We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.

Close cookie message
×
Hostname: page-component-745bb68f8f-cphqk Total loading time: 0 Render date: 2025-02-07T14:54:10.921Z Has data issue: false hasContentIssue false

Generalizing finitemodel theory

from TUTORIAL

Published online by Cambridge University Press:  30 March 2017

By
Michael Benedikt
Edited by
Viggo Stoltenberg-Hansen  and
Jouko Väänänen
Viggo Stoltenberg-Hansen
Affiliation:
Uppsala Universitet, Sweden
Jouko Väänänen
Affiliation:
University of Helsinki
Get access

Summary

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.

Introduction. ClassicalFiniteModelTheory andDescriptiveComplexity Theory [25, 17] give results about the expressiveness and complexity of logics over finite relational structures. This paper surveys work generalizing finite model theory to the situation where there is some infinite interpreted structure M where the finite relations live. We want to talk about logics that can access both the finite structure and the infinite background model; what classes are definable within such a logic, and what can we say about them with respect to computability and complexity? Answering these questions requires a suitable model of definability in the presence of built-in structure, as well as a notion of complexity appropriate when one works in an abstract setting, possibly over noneffective domains. There are several candidate approaches to logics over finite models “with a background structure”, and for each of these there are multiple complexity models one could compare against.

Type
Chapter
Information
Logic Colloquium '03 , pp. 3 - 24
Publisher: Cambridge University Press
Print publication year: 2006

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] J., Baldwin and B., Baizhanov, Local homogeneity, Submitted for publication.
[2] J., Baldwin and M., Benedikt, Stability theory, permutations of indiscernibles, and embedded finite models, Transactions of the AmericanMathematical Society, vol. 352 (2000), pp. 4937–4969.Google Scholar
[3] D.A., Barrington, N., Immerman, and H., Straubing, On uniformity within NC1, Journal of Computer and System Sciences, vol. 41 (1990), pp. 274–306.Google Scholar
[4] S., Basu, New results on quantifier elimination over real closed fields and applications to constraint databases, Journal of the ACM, vol. 46 (1999), pp. 537–555.Google Scholar
[5] O., Belagradek, A., Stolboushkin, and M., Taitslin, Extended order-generic queries, Annals of Pure and Applied Logic, vol. 97 (1999), pp. 85–125.Google Scholar
[6] M., Benedikt, G., Dong, L., Libkin, and L., Wong, Relational expressive power of constraint query languages, Journal of the ACM, vol. 45 (1998), pp. 1–34.Google Scholar
[7] M., Benedikt and L., Libkin, Unpublished notes, 1999.
[8] M., Benedikt and L., Libkin, Tree extension algebras: logics, automata, and query languages, IEEE symposium on logic in computer science, 2002, pp. 203–214.
[9] M., Benedikt, L., Libkin, T., Schwentick, and L., Segoufin, String operations in query languages, ACMsymposium on principles of database systems, 2001, pp. 183–194.
[10] O., Beyarslan and D., Marker, Personal communication, 2002.
[11] L., Blum, F., Cucker,M., Shub, and S., Smale, Complexity and real computation, Springer Verlag, 1997.
[12] A., Blumensath and E., Grädel, Automatic structures, IEEE symposium on logic in computer science, 2000, pp. 51–62.
[13] R.B., Boppana and M., Sipser, The complexity of finite functions, Handbook of theoretical computer science, volume A, Elsevier, 1990, pp. 757–804.
[14] V., Bruyre, G., Hansel, C., Michaux, and R., Villemaire, Logic and p-recognizable sets of integers, Bulletin of the Belgian Mathematical Society, vol. 1 (1994), pp. 191–238.Google Scholar
[15] E., Casanovas and M., Ziegler, Stable theories with an extra predicate, The Journal of Symbolic Logic, vol. 66 (2001), pp. 1127–1140.Google Scholar
[16] O., Chapuis and P., Koiran, Stability and saturation in the theory of computation over the reals, Annals of Pure and Applied Logic, vol. 99 (1999), pp. 1–49.Google Scholar
[17] H.-D., Ebbinghaus and J., Flum, Finite model theory, Springer Verlag, 1995.
[18] J., Flum and M., Ziegler, Pseudo-finite homogeneity and saturation, The Journal of Symbolic Logic, vol. 64 (1999), pp. 1689–1699.Google Scholar
[19] H., Fournier, Quantifier rank for parity of embedded finite models, Theoretical Computer Science, vol. 295 (2003), pp. 153–169.Google Scholar
[20] H., Fournier and P., Koiran, Lower bounds are not easier over the reals: Inside PH, ICALP, 2000, pp. 832–843.
[21] M., Garey and D., Johnson, Computers and intractability, W.H. Freeman, 1979.
[22] E., Grädel and Y., Gurevich, Metafinite model theory, Information and Computation, vol. 140 (1998), pp. 26–81.Google Scholar
[23] E., Grädel and K., Meer, Descriptive complexity theory over the real numbers, ACM symposium on theory of computing, 1995, pp. 315–324.
[24] W., Hodges,Model theory, Cambridge, 1993.
[25] N., Immerman, Descriptive complexity, Springer Verlag, 1999.
[26] P., Kanellakis, G., Kuper, and P., Revesz, Constraint query languages, Journal of Computer and System Sciences, vol. 51 (1995), pp. 26–52, Extended abstract in ACM Symposium on Principles of Database Systems, 1990, pages 299–313.Google Scholar
[27] P., Koiran, Transfer theorems via sign conditions, Information Processing Letters, vol. 81 (2002), pp. 65–69.Google Scholar
[28] G., Kuper, L., Libkin, and J., Paredaens (editors), Constraint databases, Springer Verlag, 2000.
[29] K., Meer and C., Michaux, A survey on real structural complexity theory, Bulletin of the Belgian Mathematical Society, (1997), pp. 113–148.
[30] C., Michaux, P≠NP over the nonstandard reals implies P≠NP over R, Theoretical Computer Science, vol. 133 (1994), pp. 95–104.Google Scholar
[31] J., Paredaens, J., Van den Bussche, and D., Van Gucht, First-order queries on finite structures over the reals, SIAMJournal on Computing, vol. 27 (1998), pp. 1747–1763.Google Scholar
[32] B., Poizat, Les petites caillous, 1995.
[33] N., Portier, Stabilité polynômiale des corps différentiels, The Journal of Symbolic Logic, vol. 64 (1999), no. 2, pp. 803–816.Google Scholar
[34] J.H., Reif, On threshold circuits and polynomial computation, IEEE conference on structure in complexity theory, (1987), pp. 118–123.
[35] J., Renegar, On the computational complexity and geometry of the first-order theory of the reals, Journal of Symbolic Computation, (1992), pp. 255–352.
[36] J., Schmerl, On N0-categoricity and the theory of trees, FundamentaMathematicae, vol. 94 (1977), pp. 121–128.Google Scholar
[37] L., van den Dries, Tame topology and O-minimal structures, Cambridge, 1998.

Save book to Kindle

To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.

Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.

Find out more about the Kindle Personal Document Service.

Available formats
×

Save book to Dropbox

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.

Available formats
×

Save book to Google Drive

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.

Available formats
×