Download PDF - Finite models and finitely many variablesAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

Finite models and finitely many variables

Authors 1

Affiliations

  1. Department of Computer Science, University of Wales Swansea, Swansea, SA2 8PP, U.K.

Abstract

This paper is a survey of results on finite variable logics in finite model theory. It focusses on the common underlying techniques that unite many such results.

Bibliography

  1. S. Abiteboul, M. Y. Vardi, and V. Vianu, Computing with infinitary logic, Theoretical Computer Science, 149:101-128, 1995.
  2. S. Abiteboul, M. Y. Vardi, and V. Vianu, Fixpoint logics, relational machines, and computational complexity, J. ACM, 44:30-56, 1997.
  3. S. Abiteboul and V. Vianu, Datalog extensions for database queries and updates, J. of Computer and System Sciences, 43:62-124, 1991.
  4. S. Abiteboul and V. Vianu, Generic computation and its complexity, in: Proc. 23rd ACM Symposium on the Theory of Computing, 1991.
  5. S. Abiteboul and V. Vianu, Computing with first-order logic, J. of Computer and System Sciences, 50(2):309-335, 1995.
  6. P. Aczel, An introduction to inductive definitions, in: J. Barwise, editor, Handbook of Mathematical Logic. North Holland, 1977.
  7. F. Afrati, S. S. Cosmadakis, and M. Yannakakis, On Datalog vs. polynomial time, J. Computer and System Sciences, 51:177-196, 1995.
  8. A.V. Aho and J.D. Ullman, Universality of data retrieval languages, in: Proc. 6th ACM Symposium on Principles of Programming Languages, pages 110-117, 1979.
  9. M. Ajtai and R. Fagin, Reachability is harder for directed than for undirected graphs, Journal of Symbolic Logic, 55:113-150, 1990.
  10. J. Barwise, On Moschovakis closure ordinals, Journal of Symbolic Logic, 42:292-296, 1977.
  11. A. Blass, Y. Gurevich, and D. Kozen, A zero-one law for logic with a fixed point operator Information and Control, 67:70-90, 1985.
  12. B. Bollobás, Random Graphs, Academic Press, 1985.
  13. A. Chandra and D. Harel, Structure and complexity of relational queries, Journal of Computer and System Sciences, 25:99-128, 1982.
  14. A. Dawar, Feasible Computation through Model Theory. PhD thesis, University of Pennsylvania, 1993.
  15. A. Dawar, A restricted second order logic for finite structures, Information and Computation, to appear.
  16. A. Dawar, Types and indiscernibles in finite models, in: J.A. Makowsky, editor, Logic Colloquium '95, Lecture Notes in Logic. Springer, 1997, to appear.
  17. A. Dawar and L. Hella, The expressive power of finitely many generalized quantifiers, Information and Computation, 123(2):172-184, 1995.
  18. A. Dawar, L. Hella, and Ph. G. Kolaitis, Implicit definability and infinitary logic in finite model theory, in: Z. Fülöp and F. Gécseg, editors, ICALP95, volume 944 of LNCS, pages 624-635. Springer, 1995.
  19. A. Dawar, S. Lindell, and S. Weinstein, Infinitary logic and inductive definability over finite structures, Information and Computation, 119(2):160-175, 1995.
  20. A. Dawar, S. Lindell, and S. Weinstein, First order logic, fixed point logic and linear order, in: H. Kleine-Büning, editor, Computer Science Logic '95, volume 1092 of LNCS, pages 161-177. Springer, 1996.
  21. M. de Rougemont, Second-order and inductive definability on finite structures, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 33:47-63, 1987.
  22. A. Durand, C. Lautemann, and T. Schwentick, Subclasses of binary NP, Technischer Report 1/96, Institut für Informatik, Johannes Gutenberg-Universität Mainz, 1995.
  23. E. Engeler, Formal Languages: Automata and Structures, Markham, 1968.
  24. R. Fagin, Generalized first-order spectra and polynomial-time recognizable sets, in: R. M. Karp, editor, Complexity of Computation, SIAM-AMS Proceedings, Vol 7, pages 43-73, 1974.
  25. R. Fagin, Probabilities on finite models, Journal of Symbolic Logic, 41(1):50-58, March 1976.
  26. R. Fagin, L.J. Stockmeyer, and M.Y. Vardi, On monadic NP vs. monadic co-NP, Information and Computation, 120(1):78-92, 1995.
  27. Y. V. Glebskiĭ, D. I. Kogan, M.I. Ligon'kiĭ, and V. A. Talanov, Range and degree of realizability of formulas in the restricted predicate calculus, Kibernetika, 2:17-28, 1969.
  28. M. Grohe, Inversion of the Lk-invariants is hard, Unpublished manuscript.
  29. M. Grohe, Equivalence in finite-variable logics is complete for polynomial time, in: Proceedings of the 37th Annual Symposium on the Foundations of Computer Science. IEEE Computer Society Press, 1996.
  30. M. Grohe, Large finite structures with few Lk-types, in: Proceedings of the 12th Annual IEEE Symposium on Logic in Computer Science. IEEE Computer Society Press, 1997.
  31. Y. Gurevich, Logic and the challenge of computer science, in: E. Börger, editor, Current Trends in Theoretical Computer Science, pages 1-57. Computer Science Press, 1988.
  32. Y. Gurevich, N. Immerman, and S. Shelah, McColm's conjecture, in: Proc. 9th IEEE Symp. on Logic in Computer Science, pages 10-19, 1994.
  33. Y. Gurevich and S. Shelah, On finite rigid structures, Journal of Symbolic Logic, 61:549-562, 1996.
  34. I. Hodkinson, Finite variable logics, Revised version of Bull. Europ. Assoc. Theor. Comp. Sci. 51 (Oct 1993) 111-140, 1996.
  35. N. Immerman, Upper and lower bounds for first-order expressibility, J. of Computer and System Sciences, 25:76-98, 1982.
  36. N. Immerman, Relational queries computable in polynomial time, Information and Control, 68:86-104, 1986.
  37. N. Immerman, DSPACE[nk]=VAR[k+1], in: Proc. 6th IEEE Symp. on Structure in Complexity Theory, pages 334-340, 1991.
  38. Ph.G. Kolaitis, On asymptotic probabilities of inductive queries and their decision problem, in: R. Parikh, editor, Logics of Programs, volume 193 of LNCS, pages 153-166. Springer, 1985.
  39. Ph.G. Kolaitis and M.Y. Vardi, The decision problem for the probabilities of higher-order properties, in: Proc. 19th ACM Symposium on Theory of Computing, pages 425-435, 1987.
  40. Ph.G. Kolaitis and M.Y. Vardi, Fixpoint logic vs. infinitary logic in finite-model theory, in: Proc. 7th IEEE Symp. on Logic in Computer Science, pages 46-57, 1992.
  41. Ph.G. Kolaitis and M.Y. Vardi, Infinitary logics and 0-1 laws, Information and Computation, 98(2):258-294, 1992.
  42. Ph.G. Kolaitis and M.Y. Vardi, On the expressive power of Datalog - tools and a case study. J. Computer and System Sciences, 51:110-134, 1995.
  43. Ph.G. Kolaitis and M.Y. Vardi, On the expressive power of variable confined logics, in: Proc. 11th IEEE Symp. on Logic in Computer Science, pages 348-359, 1996.
  44. J.F. Lynch, Infinitary logics and very sparse random graphs, in: Proc. 8th IEEE Symposium on Logic in Computer Science, pages 191-198, 1993.
  45. M. McArthur, The asymptotic behaviour of Lk_{∞ω} on sparse random graphs, in: R.B. Boppana and J.F. Lynch, editors, Logic and Random Structures, pages 53-63. AMS, 1997.
  46. M. McArthur and J. Spencer, Nonconvergence for sparse random graphs, manuscript.
  47. G. L. McColm, Parametrization over inductive relations of a bounded number of variables, Annals of Pure and Applied Logic, 48:103-134, 1990.
  48. G. L. McColm, When is arithmetic possible?, Annals of Pure and Applied Logic, 50:29-51, 1990.
  49. Y. N. Moschovakis, Elementary Induction on Abstract Structures, North Holland, 1974.
  50. M. Otto, Bounded Variable Logics and Counting, volume 9 of Lecture Notes in Logic, Springer, 1997.
  51. B. Poizat, Deux ou trois choses que je sais de Ln, J. Symbolic Logic, 47(3):641-658, 1982.
  52. E. Rosen, S. Shelah, and S. Weinstein, k-universal finite graphs, in: R.B. Boppana and J.F. Lynch, editors, Logic and Random Structures, pages 65-77. AMS, 1997.
  53. E. Rosen and S. Weinstein, Preservation theorems in finite model theory, in: D. Leivant, editor, Logic and Computational Complexity, volume 960 of LNCS, pages 480-503. Springer, 1995.
  54. A. Rubin, Free Algebras in Von Neumann-Bernays-Godel Set Theory and Positive Elementary Inductions in Reasonable Structures, PhD thesis, California Institute of Technology, 1975.
  55. A. Stolboushkin, Axiomatizable classes of finite models and definability of linear order, in: Proc. 7th IEEE Symp. on Logic in Computer Science, 1992.
  56. S. Thomas, Theories with finitely many models, J. Symbolic Logic, 51:374-376, 1986.
  57. S. Thomas, Theories with finitely many models II, Unpublished manuscript, 1989.
  58. J. Tiuryn and P. Urzyczyn, Some relationships between logics of programs and complexity theory, Theoretical Computer Science, 60:83-108, 1988.
  59. J. Tyszkiewicz, On asymptotic probabilities in logics that capture DSPACE(log n), in: Proc. TAPSOFT'93, volume 668 of LNCS. Springer, 1993.
  60. M. Y. Vardi, The complexity of relational query languages, in: Proc. 14th ACM Symposium on the Theory of Computing, pages 137-146, 1982.
Banach Center Publications
1999/46/1
Export to PBN, Opens in new tab
Pages:
93-117
Main language of publication
English
Published
1999
Exact and natural sciences