# Finite models and finitely many variables

Banach Center Publications (1999)

- Volume: 46, Issue: 1, page 93-117
- ISSN: 0137-6934

## Access Full Article

top## Abstract

top## How to cite

topDawar, Anuj. "Finite models and finitely many variables." Banach Center Publications 46.1 (1999): 93-117. <http://eudml.org/doc/208925>.

@article{Dawar1999,

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.},

author = {Dawar, Anuj},

journal = {Banach Center Publications},

keywords = {finite models; fixpoint logics; finite variable logics; complexity classes; survey},

language = {eng},

number = {1},

pages = {93-117},

title = {Finite models and finitely many variables},

url = {http://eudml.org/doc/208925},

volume = {46},

year = {1999},

}

TY - JOUR

AU - Dawar, Anuj

TI - Finite models and finitely many variables

JO - Banach Center Publications

PY - 1999

VL - 46

IS - 1

SP - 93

EP - 117

AB - 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.

LA - eng

KW - finite models; fixpoint logics; finite variable logics; complexity classes; survey

UR - http://eudml.org/doc/208925

ER -

## References

top- [1] S. Abiteboul, M. Y. Vardi, and V. Vianu, Computing with infinitary logic, Theoretical Computer Science, 149:101-128, 1995. Zbl0874.68274
- [2] S. Abiteboul, M. Y. Vardi, and V. Vianu, Fixpoint logics, relational machines, and computational complexity, J. ACM, 44:30-56, 1997. Zbl0883.68070
- [3] S. Abiteboul and V. Vianu, Datalog extensions for database queries and updates, J. of Computer and System Sciences, 43:62-124, 1991. Zbl0764.68158
- [4] S. Abiteboul and V. Vianu, Generic computation and its complexity, in: Proc. 23rd ACM Symposium on the Theory of Computing, 1991. Zbl0764.68158
- [5] S. Abiteboul and V. Vianu, Computing with first-order logic, J. of Computer and System Sciences, 50(2):309-335, 1995. Zbl0827.68036
- [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. Zbl0831.68015
- [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. Zbl0708.03016
- [10] J. Barwise, On Moschovakis closure ordinals, Journal of Symbolic Logic, 42:292-296, 1977. Zbl0367.02021
- [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. Zbl0608.68077
- [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. Zbl0511.68073
- [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. Zbl0899.03023
- [17] A. Dawar and L. Hella, The expressive power of finitely many generalized quantifiers, Information and Computation, 123(2):172-184, 1995. Zbl0849.68034
- [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. Zbl0834.68029
- [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. Zbl0652.03032
- [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. Zbl0901.68076
- [23] E. Engeler, Formal Languages: Automata and Structures, Markham, 1968. Zbl0157.01801
- [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. Zbl0303.68035
- [25] R. Fagin, Probabilities on finite models, Journal of Symbolic Logic, 41(1):50-58, March 1976. Zbl0341.02044
- [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. Zbl0835.68046
- [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 ${L}^{k}$-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. Zbl0987.03033
- [30] M. Grohe, Large finite structures with few ${L}^{k}$-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. Zbl0860.03029
- [34] I. Hodkinson, Finite variable logics, Revised version of Bull. Europ. Assoc. Theor. Comp. Sci. 51 (Oct 1993) 111-140, 1996. Zbl0788.03051
- [35] N. Immerman, Upper and lower bounds for first-order expressibility, J. of Computer and System Sciences, 25:76-98, 1982. Zbl0503.68032
- [36] N. Immerman, Relational queries computable in polynomial time, Information and Control, 68:86-104, 1986. Zbl0612.68086
- [37] N. Immerman, $DSPACE\left[{n}^{k}\right]=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. Zbl0762.03016
- [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 ${L}_{\infty \omega}^{k}$ on sparse random graphs, in: R.B. Boppana and J.F. Lynch, editors, Logic and Random Structures, pages 53-63. AMS, 1997. Zbl0882.03037
- [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. Zbl0705.03019
- [48] G. L. McColm, When is arithmetic possible?, Annals of Pure and Applied Logic, 50:29-51, 1990. Zbl0711.03018
- [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 ${L}_{n}$, J. Symbolic Logic, 47(3):641-658, 1982. Zbl0507.03014
- [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. Zbl0882.03034
- [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. Zbl0622.03022
- [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. Zbl0652.03028
- [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.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.