Finite models and finitely many variables

Dawar, Anuj

Banach Center Publications, Tome 50 (1999), p. 93-117 / Harvested from The Polish Digital Mathematics Library

Résumé

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.

Détail

Publié le : 1999-01-01

Zbl 0936.03032

EUDML-ID : urn:eudml:doc:208925

Bibliographie

[000] [1] S. Abiteboul, M. Y. Vardi, and V. Vianu, Computing with infinitary logic, Theoretical Computer Science, 149:101-128, 1995. | Zbl 0874.68274

[001] [2] S. Abiteboul, M. Y. Vardi, and V. Vianu, Fixpoint logics, relational machines, and computational complexity, J. ACM, 44:30-56, 1997. | Zbl 0883.68070

[002] [3] S. Abiteboul and V. Vianu, Datalog extensions for database queries and updates, J. of Computer and System Sciences, 43:62-124, 1991. | Zbl 0764.68158

[003] [4] S. Abiteboul and V. Vianu, Generic computation and its complexity, in: Proc. 23rd ACM Symposium on the Theory of Computing, 1991. | Zbl 0764.68158

[004] [5] S. Abiteboul and V. Vianu, Computing with first-order logic, J. of Computer and System Sciences, 50(2):309-335, 1995. | Zbl 0827.68036

[005] [6] P. Aczel, An introduction to inductive definitions, in: J. Barwise, editor, Handbook of Mathematical Logic. North Holland, 1977.

[006] [7] F. Afrati, S. S. Cosmadakis, and M. Yannakakis, On Datalog vs. polynomial time, J. Computer and System Sciences, 51:177-196, 1995. | Zbl 0831.68015

[007] [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.

[008] [9] M. Ajtai and R. Fagin, Reachability is harder for directed than for undirected graphs, Journal of Symbolic Logic, 55:113-150, 1990. | Zbl 0708.03016

[009] [10] J. Barwise, On Moschovakis closure ordinals, Journal of Symbolic Logic, 42:292-296, 1977. | Zbl 0367.02021

[010] [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. | Zbl 0608.68077

[011] [12] B. Bollobás, Random Graphs, Academic Press, 1985.

[012] [13] A. Chandra and D. Harel, Structure and complexity of relational queries, Journal of Computer and System Sciences, 25:99-128, 1982. | Zbl 0511.68073

[013] [14] A. Dawar, Feasible Computation through Model Theory. PhD thesis, University of Pennsylvania, 1993.

[014] [15] A. Dawar, A restricted second order logic for finite structures, Information and Computation, to appear.

[015] [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. | Zbl 0899.03023

[016] [17] A. Dawar and L. Hella, The expressive power of finitely many generalized quantifiers, Information and Computation, 123(2):172-184, 1995. | Zbl 0849.68034

[017] [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.

[018] [19] A. Dawar, S. Lindell, and S. Weinstein, Infinitary logic and inductive definability over finite structures, Information and Computation, 119(2):160-175, 1995. | Zbl 0834.68029

[019] [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.

[020] [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. | Zbl 0652.03032

[021] [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. | Zbl 0901.68076

[022] [23] E. Engeler, Formal Languages: Automata and Structures, Markham, 1968. | Zbl 0157.01801

[023] [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. | Zbl 0303.68035

[024] [25] R. Fagin, Probabilities on finite models, Journal of Symbolic Logic, 41(1):50-58, March 1976. | Zbl 0341.02044

[025] [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. | Zbl 0835.68046

[026] [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.

[027] [28] M. Grohe, Inversion of the $L^k$-invariants is hard, Unpublished manuscript.

[028] [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. | Zbl 0987.03033

[029] [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.

[030] [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.

[031] [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.

[032] [33] Y. Gurevich and S. Shelah, On finite rigid structures, Journal of Symbolic Logic, 61:549-562, 1996. | Zbl 0860.03029

[033] [34] I. Hodkinson, Finite variable logics, Revised version of Bull. Europ. Assoc. Theor. Comp. Sci. 51 (Oct 1993) 111-140, 1996. | Zbl 0788.03051

[034] [35] N. Immerman, Upper and lower bounds for first-order expressibility, J. of Computer and System Sciences, 25:76-98, 1982. | Zbl 0503.68032

[035] [36] N. Immerman, Relational queries computable in polynomial time, Information and Control, 68:86-104, 1986. | Zbl 0612.68086

[036] [37] N. Immerman, $DSPACE[n^k]=VAR[k+1]$, in: Proc. 6th IEEE Symp. on Structure in Complexity Theory, pages 334-340, 1991.

[037] [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.

[038] [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.

[039] [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.

[040] [41] Ph.G. Kolaitis and M.Y. Vardi, Infinitary logics and 0-1 laws, Information and Computation, 98(2):258-294, 1992. | Zbl 0762.03016

[041] [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.

[042] [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.

[043] [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.

[044] [45] M. McArthur, The asymptotic behaviour of $L^{k}_{∞ω}$ on sparse random graphs, in: R.B. Boppana and J.F. Lynch, editors, Logic and Random Structures, pages 53-63. AMS, 1997. | Zbl 0882.03037

[045] [46] M. McArthur and J. Spencer, Nonconvergence for sparse random graphs, manuscript.

[046] [47] G. L. McColm, Parametrization over inductive relations of a bounded number of variables, Annals of Pure and Applied Logic, 48:103-134, 1990. | Zbl 0705.03019

[047] [48] G. L. McColm, When is arithmetic possible?, Annals of Pure and Applied Logic, 50:29-51, 1990. | Zbl 0711.03018

[048] [49] Y. N. Moschovakis, Elementary Induction on Abstract Structures, North Holland, 1974.

[049] [50] M. Otto, Bounded Variable Logics and Counting, volume 9 of Lecture Notes in Logic, Springer, 1997.

[050] [51] B. Poizat, Deux ou trois choses que je sais de $L_n$, J. Symbolic Logic, 47(3):641-658, 1982. | Zbl 0507.03014

[051] [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. | Zbl 0882.03034

[052] [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.

[053] [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.

[054] [55] A. Stolboushkin, Axiomatizable classes of finite models and definability of linear order, in: Proc. 7th IEEE Symp. on Logic in Computer Science, 1992.

[055] [56] S. Thomas, Theories with finitely many models, J. Symbolic Logic, 51:374-376, 1986. | Zbl 0622.03022

[056] [57] S. Thomas, Theories with finitely many models II, Unpublished manuscript, 1989.

[057] [58] J. Tiuryn and P. Urzyczyn, Some relationships between logics of programs and complexity theory, Theoretical Computer Science, 60:83-108, 1988. | Zbl 0652.03028

[058] [59] J. Tyszkiewicz, On asymptotic probabilities in logics that capture DSPACE(log n), in: Proc. TAPSOFT'93, volume 668 of LNCS. Springer, 1993.

[059] [60] M. Y. Vardi, The complexity of relational query languages, in: Proc. 14th ACM Symposium on the Theory of Computing, pages 137-146, 1982.