Hostname: page-component-cd9895bd7-jn8rn Total loading time: 0 Render date: 2024-12-25T02:03:57.187Z Has data issue: false hasContentIssue false
  • English
  • Français

Almost Everywhere Equivalence of Logics in Finite Model Theory

Published online by Cambridge University Press:  15 January 2014

Lauri Hella ,
Phokion G. Kolaitis  and
Kerkko Luosto
Lauri Hella
Affiliation:
Department of Mathematics, P.O. BOX 4, 00014, University of Helsinki, Finland. E-mail: [email protected]
Phokion G. Kolaitis
Affiliation:
Computer Science Department UC Santa Cruz, Santa Cruz, California 95064, USA E-mail: [email protected]
Kerkko Luosto
Affiliation:
Department of Mathematics, P.O. BOX 4, 00014, University of Helsinki, Finland E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We introduce a new framework for classifying logics on finite structures and studying their expressive power. This framework is based on the concept of almost everywhere equivalence of logics, that is to say, two logics having the same expressive power on a class of asymptotic measure 1. More precisely, if L, L′ are two logics and μ is an asymptotic measure on finite structures, then L ≡a.e.L′ (μ) means that there is a class C of finite structures with μ(C) = 1 and such that L and L′ define the same queries on C. We carry out a systematic investigation of ≡a.e. with respect to the uniform measure and analyze the ≡a.e.-equivalence classes of several logics that have been studied extensively in finite model theory. Moreover, we explore connections with descriptive complexity theory and examine the status of certain classical results of model theory in the context of this new framework.

Type
Research Article
Information
Bulletin of Symbolic Logic , Volume 2 , Issue 4 , December 1996 , pp. 422 - 443
Copyright
Copyright © Association for Symbolic Logic 1996

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

REFERENCES

[1] Abiteboul, S., Hull, R., and Vianu, V., Foundations of databases, Addison-Wesley, 1995.Google Scholar
[2] Abiteboul, S. and Vianu, V., Fixpoint extensions of first-order logic and Datalog-like languages, Proceedings of the 4th IEEE symposium on logic in computer science, 1989, pp. 71–79.Google Scholar
[3] Babai, L., Erdős, P., and Selkow, S. M., Random graph isomorphism, SIAM Journal on Computing, vol. 9 (1980), pp. 628–635.CrossRefGoogle Scholar
[4] Cai, J., Fürer, M., and Immerman, N., An optimal lower bound on the number of variables for graph identification, Combinatorica, vol. 12 (1992), no. 4, pp. 389–410.CrossRefGoogle Scholar
[5] Chandra, A. and Harel, D., Structure and complexity of relational queries, Journal of Computer and System Sciences, vol. 25 (1982), pp. 99–128.CrossRefGoogle Scholar
[6] Dawar, A., Lindell, S., and Weinstein, S., Infinitary logic and inductive definability over finite structures, Information and Control, vol. 119 (1995), no. 2, pp. 160–175.Google Scholar
[7] Erdős, P. and Rényi, A., On the evolution of random graphs, Publications of the Mathematical Institute of the Hungarian Academy of Sciences, vol. 7 (1960), pp. 17–61.Google Scholar
[8] Fagin, R., Generalized first-order spectra and polynomial-time recognizable sets, Complexity of computation (Karp, R.M., editor), SIAM-AMS Proceedings, vol. 7, 1974, pp. 43–73.Google Scholar
[9] Fagin, R., Monadic generalized spectra, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 21 (1975), pp. 89–96.CrossRefGoogle Scholar
[10] Fagin, R., Probabilities on finite models, The Journal of Symbolic Logic, vol. 41 (1976), pp. 50–58.CrossRefGoogle Scholar
[11] Glebskii, Y. V., Kogan, D. I., Liogonki, M. I., and Talanov, V A., Range and degree of realizability of formulas in the restricted predicate calculus, Cybernetics, vol. 5 (1969), pp. 142–154.CrossRefGoogle Scholar
[12] Grumbach, S., A paradox in database theory, 3rd ERCIM database research group workshop on updates and constraints handling in advanced database systems, ERCIM-94-W004 CNR, 1992, pp. 130–143.Google Scholar
[13] Gurevich, Y., Toward logic tailored for computational complexity, Computation and proof theory (Ricther, M. M. et al., editors), Lecture Notes in Mathematics, no. 1104, Springer-Verlag, 1984, pp. 175–216.CrossRefGoogle Scholar
[14] Gurevich, Y., Logic and the challenge of computer science, Current trends in theoretical computer science (Börger, E., editor), Computer Science Press, 1988, pp. 1–57.Google Scholar
[15] Gurevich, Y. and Shelah, S., Fixed-point extensions offirst-order logic, Annals of Pure and Applied Logic, vol. 32 (1986), pp. 265–280.CrossRefGoogle Scholar
[16] Hella, L., Kolaitis, Ph. G., and Luosto., K., How to define a linear order on finite models, Proceedings ofthe 9th IEEE symposium on logic in computer science, 1994, pp. 40–49.Google Scholar
[17] Hella, L., Luosto, K., and Väänänen, J., The hierarchy theorem for generalized quantifiers, to appear in the The Journal of Symbolic Logic, 1995.Google Scholar
[18] Immerman, N., Relational queries computable in polynomial time, Information and Control, vol. 68 (1986), pp. 86–104.CrossRefGoogle Scholar
[19] Immerman, N., Languages that capture complexity classes, SIAM Journal of Computing, vol. 16 (1987), pp. 760–778.CrossRefGoogle Scholar
[20] Immerman, N. and Kozen, D., Definability with bounded number of bound variables, Information and Computation, vol. 83 (1989), pp. 121–139.CrossRefGoogle Scholar
[21] Karp, R., Probabilistic analysis of a canonical algorithm for graphs, Proceedings of Symposia in Pure Mathematics, no. 34, American Mathematical Society, 1979.CrossRefGoogle Scholar
[22] Kaufmann, M. and Shelah, S., On random models of finite power and monadic logic, Discrete Mathematics, vol. 54 (1985), pp. 285–293.CrossRefGoogle Scholar
[23] Kolaitis, Ph. G., Implicit definability on finite structures and unambiguous computations, Proceedings of the 5th IEEE symposium on logic in computer science, 1990, pp. 168–180.Google Scholar
[24] Kolaitis, Ph. G. and Väänànen, J. K., Generalized quantifiers and pebble games on finite structures, Annals of Pure and Applied Logic, vol. 74 (1995), no. 1, pp. 23–75.CrossRefGoogle Scholar
[25] Kolaitis, Ph. G. and Vardi, M. Y., Infinitary logic and 0-1 laws , Information and Computation, vol. 98 (1992), pp. 258–294, special issue: selections from the fifth annual IEEE symposium on logic in computer science.CrossRefGoogle Scholar
[26] Lindström, P., First order predicate logic with generalized quantifiers, Theoria, vol. 32 (1966), pp. 186–195.CrossRefGoogle Scholar
[27] Lynch, J., Infinitary logics and very sparse random graphs, Proceedings of the 8th IEEE symposium on logic in computer science, 1993, pp. 191–198.Google Scholar
[28] Lynch, J. and Tyszkiewicz, J., The infinitary logic of sparse random graphs, Proceedings of the 10th IEEE symposium on logic in computer science, 1995, pp. 46–53.Google Scholar
[29] McArthur, M., Convergence and 0-1 laws for under arbitrary measures , Computer science logic (Pacholski, L. and Tiuryn, J., editors), Springer-Verlag, 1995, CSL '94, pp. 228–241.CrossRefGoogle Scholar
[30] Mostowski, A., On a generalization of quantifiers, Fundamenda Mathematicae, vol. 44 (1957), pp. 12–36.CrossRefGoogle Scholar
[31] Shelah, S. and Spencer, J., Zero-one laws for sparse random graphs, Journal of the American Mathematical Society, vol. 1 (1988), pp. 97–115.CrossRefGoogle Scholar
[32] Vardi, M. Y., The complexity of relational query languages, Proceedings of the 14th ACM symposium on theory of computing, 1982, pp. 137–146.Google Scholar