Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-29T02:03:08.406Z Has data issue: false hasContentIssue false
  • English
  • Français

Notions of locality and their logical characterizations over finite models

Published online by Cambridge University Press:  12 March 2014

Lauri Hella ,
Leonid Libkin  and
Juha Nurmonen
Lauri Hella
Affiliation:
Department of Mathematics, P.O. Box 4 (Yliopistonkatu 5), 00014 University of Helsinki, Finland, E-mail: [email protected]
Leonid Libkin
Affiliation:
Bell Laboratories, 600 Mountain Avenue, Murray Hill, NJ 07974, USA, E-mail: [email protected]
Juha Nurmonen
Affiliation:
Department of Mathematics and Computer Science, University of Leicester, University Road, Leicester Lei 7RH, UK, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Many known tools for proving expressibility bounds for first-ordér logic are based on one of several locality properties. In this paper we characterize the relationship between those notions of locality. We note that Gaifman's locality theorem gives rise to two notions: one deals with sentences and one with open formulae. We prove that the former implies Hanf's notion of locality, which in turn implies Gaifman's locality for open formulae. Each of these implies the bounded degree property, which is one of the easiest tools for proving expressibility bounds. These results apply beyond the first-order case. We use them to derive expressibility bounds for first-order logic with unary quantifiers and counting. We also characterize the notions of locality on structures of small degree.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 64 , Issue 4 , December 1999 , pp. 1751 - 1773
Copyright
Copyright © Association for Symbolic Logic 1999

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]Ajtai, M. and Fagin, R., Reachability is harder for directed than for undirected graphs, this Journal, vol. 55(1) (03 1990), pp. 113–150.Google Scholar
[3]Barrington, D.M., Immerman, N., and Straubing, H., On uniformity within NC1, Journal of Comput. and Syst. Sci., vol. 41 (1990), pp. 274–306.CrossRefGoogle Scholar
[4]Benedikt, M., Griffin, T., and Libkin, L., Verifiable properties of database transactions, Information and Computation, vol. 145 (1998), pp. 57–88.CrossRefGoogle Scholar
[5]Benedikt, M. and Libkin, L., On the structure of queries in constraint query languages, Proceedings of 11th IEEE Symposium on Logic in Computer Science, New Brunswick, NJ, 07 1996, pp. 25–34.Google Scholar
[6]Dong, G., Libkin, L., and Wong, L., Local properties of query languages, Theoretical Computer Science (to appear), Extended abstract in Proceedings of International Conference on Database Theory, Springer Lecture Notes in Computer Science 1186, 1997, pages 140–154.Google Scholar
[7]Ebbinghaus, H.-D., Extended logics: the general framework, Model-theoretic logics (Barwise, J. and Feferman, S., editors), Springer-Verlag, 1985, pp. 25–76.Google Scholar
[8]Ebbinghaus, H.-D. and Flum, J., Finite model theory, Springer-Verlag, 1995.Google Scholar
[9]Etessami, K., Counting quantifiers, successor relations, and logarithmic space, Journal of Computer and System Sciences, vol. 54 (1997), pp. 400–411.CrossRefGoogle Scholar
[10]Fagin, R., Easier ways to win logical games, Descriptive complexity and finite models (Immerman, N. and Kolaitis, Ph., editors), American Mathematical Society, 1997, pp. 1–32.Google Scholar
[11]Fagin, R., Stockmeyer, L., and Vardi, M., On monadic NP vs. monadic co-NP, Information and Computation, vol. 120 (1995), pp. 78–92.CrossRefGoogle Scholar
[12]Gaifman, H., On local and non-local properties, Proceedings of the Herbrand Symposium, Logic Colloquium '81, North Holland, 1982.Google Scholar
[13]Grohe, M. and Schwentick, T., Locality of order-invariant first-order formulas, Proceedings of conference on mathematical foundations of computer science (MFCS'98), Lecture Notes in Computer Science, vol. 1450, Springer-Verlag, 1998, pp. 437–445.Google Scholar
[14]Grumbach, S., Libkin, L., Milo, T., and Wong, L., Query languages for bags: expressive power and complexity, SIGACT News, vol. 27 (1996), pp. 30–37.CrossRefGoogle Scholar
[15]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
[16]Hanf, W., Model-theoretic methods in the study of elementary logic, The theory of models (Addison, J.W.et al., editors), North Holland, 1965, pp. 132–145.Google Scholar
[17]Hella, L., Logical hierarchies in PTIME, Information and Computation, vol. 129 (1996), pp. 1–19.CrossRefGoogle Scholar
[18]Immerman, N., Descriptive complexity: A logician's approach to computation, Notices of the American Mathemtical Society, vol. 42 (1995), pp. 1127–1133.Google Scholar
[19]Immerman, N. and Lander, E., Describing graphs: A first order approach to graph canonization, Complexity theory retrospective, Springer-Verlag, Berlin, 1990.Google Scholar
[20]Kolaitis, Ph. and Väänänen, J., Generalized quantifiers and pebble games on finite structures, Annals of Pure and Applied Logic, vol. 74 (1995), pp. 23–75.CrossRefGoogle Scholar
[21]Libkin, L., On the forms of locality over finite models, Proceedings of 12th IEEE Symposium on Logic in Computer Science, Warsaw, Poland, 06-07 1996, pp. 204–215.Google Scholar
[22]Libkin, L. and Wong, L., Query languages for bags and aggregate functions, Journal of Computer and System Sciences, vol. 55 (1997), pp. 241–272.CrossRefGoogle Scholar
[23]Luosto, K., Hierarchies of monadic generalized quantifiers, this Journal (to appear).Google Scholar
[24]Nurmonen, J., On winning strategies with unary quantifiers, Journal of Logic and Computation, vol. 6 (1996), pp. 779–798.CrossRefGoogle Scholar
[25]Nurmonen, J., Unary quantifiers and finite structures, Ph.D. thesis, University of Helsinki, 1996.Google Scholar
[26]Nurmonen, J., Counting modulo quantifiers on finite structures, Information and Computation (to appear), Extended abstract in Proceedings of 11th IEEE Symposium on Logic in Computer Science, New Brunswick, NJ, 07 1996, pages 484–493.Google Scholar
[27]Schwentick, T., On winning Ehrenfeucht games and monadic NP, Annals of Pure and Applied Logic, vol. 79 (1996), pp. 61–92.CrossRefGoogle Scholar