PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
1999 | 46 | 1 | 93-117
Tytuł artykułu

Finite models and finitely many variables

Autorzy
Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Słowa kluczowe
Rocznik
Tom
46
Numer
1
Strony
93-117
Opis fizyczny
Daty
wydano
1999
Twórcy
autor
  • Department of Computer Science, University of Wales Swansea, Swansea, SA2 8PP, U.K.
Bibliografia
  • [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 $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.
  • [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.
  • [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[n^k]=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 $L^{k}_{∞ω}$ 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 $L_n$, 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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-bcpv46i1p93bwm
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.