Finite models and finitely many variables

 Access to full text

 Full (PDF)

1. [1] S. Abiteboul, M. Y. Vardi, and V. Vianu, Computing with infinitary logic, Theoretical Computer Science, 149:101-128, 1995. Zbl0874.68274
2. [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. [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. [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. [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. [6] P. Aczel, An introduction to inductive definitions, in: J. Barwise, editor, Handbook of Mathematical Logic. North Holland, 1977. 
7. [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. [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. [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. [10] J. Barwise, On Moschovakis closure ordinals, Journal of Symbolic Logic, 42:292-296, 1977. Zbl0367.02021
11. [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. [12] B. Bollobás, Random Graphs, Academic Press, 1985. 
13. [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. [14] A. Dawar, Feasible Computation through Model Theory. PhD thesis, University of Pennsylvania, 1993. 
15. [15] A. Dawar, A restricted second order logic for finite structures, Information and Computation, to appear. 
16. [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. [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. [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. [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. [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. [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. [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. [23] E. Engeler, Formal Languages: Automata and Structures, Markham, 1968. Zbl0157.01801
24. [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. [25] R. Fagin, Probabilities on finite models, Journal of Symbolic Logic, 41(1):50-58, March 1976. Zbl0341.02044
26. [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. [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. [28] M. Grohe, Inversion of the $L^k$-invariants is hard, Unpublished manuscript. 
29. [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. [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. [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. [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. [33] Y. Gurevich and S. Shelah, On finite rigid structures, Journal of Symbolic Logic, 61:549-562, 1996. Zbl0860.03029
34. [34] I. Hodkinson, Finite variable logics, Revised version of Bull. Europ. Assoc. Theor. Comp. Sci. 51 (Oct 1993) 111-140, 1996. Zbl0788.03051
35. [35] N. Immerman, Upper and lower bounds for first-order expressibility, J. of Computer and System Sciences, 25:76-98, 1982. Zbl0503.68032
36. [36] N. Immerman, Relational queries computable in polynomial time, Information and Control, 68:86-104, 1986. Zbl0612.68086
37. [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. [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. [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. [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. [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. [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. [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. [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. [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. [46] M. McArthur and J. Spencer, Nonconvergence for sparse random graphs, manuscript. 
47. [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. [48] G. L. McColm, When is arithmetic possible?, Annals of Pure and Applied Logic, 50:29-51, 1990. Zbl0711.03018
49. [49] Y. N. Moschovakis, Elementary Induction on Abstract Structures, North Holland, 1974. 
50. [50] M. Otto, Bounded Variable Logics and Counting, volume 9 of Lecture Notes in Logic, Springer, 1997. 
51. [51] B. Poizat, Deux ou trois choses que je sais de $L_n$, J. Symbolic Logic, 47(3):641-658, 1982. Zbl0507.03014
52. [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. [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. [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. [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. [56] S. Thomas, Theories with finitely many models, J. Symbolic Logic, 51:374-376, 1986. Zbl0622.03022
57. [57] S. Thomas, Theories with finitely many models II, Unpublished manuscript, 1989. 
58. [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. [59] J. Tyszkiewicz, On asymptotic probabilities in logics that capture DSPACE(log n), in: Proc. TAPSOFT'93, volume 668 of LNCS. Springer, 1993. 
60. [60] M. Y. Vardi, The complexity of relational query languages, in: Proc. 14th ACM Symposium on the Theory of Computing, pages 137-146, 1982.