Pebble games in model theory

1. Ajtai, M., Fagin, R.: Reachability is harder for directed than for undirected finite graphs. J. Symbolic Logic 55 (1990) 113–150

   Google Scholar 

2. Barwise, J.: On Moschovakis closure ordinals. J. Symbolic Logic 42 (1977) 292–296

   Google Scholar 

3. Blass, A., Gurevich, Y., Kozen, D.: A zero-one law for logic with a fixed point operator. Inform. and Control 67 (1985) 70–90

   Google Scholar 

4. Büchi, J.: Weak second-order arithmetic and finite automata. Z. Math. Logik Grundlagen Math. 6 (1960) 66–92

   Google Scholar 

5. Compton, K.: A logical approach to asymptotic combinatorics I. first order properties. Adv. Math. 65 (1987) 65–96

   Google Scholar 

6. Compton, K.: A logical approach to asymptotic combinatorics II: monadic second-order properties. J. Comb. Theory, Ser. A 50 (1989) 110–131

   Google Scholar 

7. Coppersmith, D.: A left coset composed of n-cycles. Research Report rc 19511, IBM (1994)

   Google Scholar 

8. de Rougemont, M.: Second-order and inductive definability on finite structures. Z. Math. Logik Grundlagen Math. 33 (1987) 47–63

   Google Scholar 

9. Ebbinghaus, H.-D., Flum, J.: Finite Model Theory. Springer-Verlag (1995)

   Google Scholar 

10. Ehrenfeucht, A.: An application of games to the completeness problem for formalized theories. Fund. Math. 49 (1961) 129–141

    Google Scholar 

11. Elgot, C.: Decision problems of finite-automata design and related arithmetics. Trans. AMS 98 (1961) 21–51

    Google Scholar 

12. Fagin, R.: Generalized first-order spectra and polynomial-time recognizable sets. Complexity of Computation. R. Karp, ed. SIAM-AMS Proc. 7, Am. Math. Soc., New York (1974) 43–73

    Google Scholar 

13. Fagin, R.: Monadic generalized spectra. Z. Math. Logik Grundlagen Math. 21 (1975) 89–96

    Google Scholar 

14. Fagin R.: Probabilities on finite models. J. Symbolic Logic 41 (1976) 50–58

    Google Scholar 

15. Fraïssé, R.: Sur quelques classifications des systéms de relations. Pub. Sci. Univ. Alger Sér. A 1 (1954) 35–182

    Google Scholar 

16. Gaifman, H.: On local and nonlocal properties. Logic Colloquium '81. J. Stern, ed. North-Holland (1982) 105–135

    Google Scholar 

17. Glebskii, Y., Kogan, D., Liogon'kii, M., Talanov, V.: Range and degree of realizability of formulas in the restricted predicate calculus. Kibernetika (Kiev) 2 (1969) 17–28; English translation: Cybernetics 5 (1972) 142–154

    Google Scholar 

18. Hanf, W.: Model-theoretic methods in the study of elementary logic. J. Addison, L. Henkin, A. Tarski, eds. The Theory of Models. North-Holland (1965) 132–145

    Google Scholar 

19. Immerman, N.: Relational queries computable in polynomial time. Inform. and Control 68 (1986) 86–104

    Google Scholar 

20. Kanellakis, P.: Elements of relational database theory. The Handbook of Theoretical Computer Science. A. Meyer, M. Nivat, M. Paterson, D. Perrin, J. van Leeuwen, eds. North-Holland (1990)

    Google Scholar 

21. Kaufmann, M.: A counterexample to the 0-1 law for existential monadic second-order logic. Internal Note #032, Computational Logic Inc. (1988)

    Google Scholar 

22. Kaufmann, M., Shelah, S.: On random models of finite power and monadic logic. Discrete Math. 54 (1985) 285–293

    Google Scholar 

23. Kolaitis, Ph.: On asymptotic probabilities of inductive queries and their decision problem. R. Parikh, ed. Logics of Programs '85. Lecture Notes in Computer Science 193, Springer-Verlag (1985) 153–166

    Google Scholar 

24. Kolaitis, Ph., Vardi, M.: The decision problem for the probabilities of higher-order properties. Proc. 19th ACM Symp. on Theory of Computing (1987) 425–435

    Google Scholar 

25. Kolaitis, Ph., Vardi, M.: Infinitary logics and 0–1 laws. Inform. and Computation 98 (1992) 258–294

    Google Scholar 

26. Ladner, R.: Application of model theoretic games to discrete linear orders and finite automata. Inform. and Control 33 (1977) 281–303

    Google Scholar 

27. Lynch, J.: Almost sure theories. Ann. Math. Logic 18 (1980) 91–135

    Google Scholar 

28. Lynch, J.: On sets of relations definable by addition. J. Symbolic Logic 47 (1982) 659–668

    Google Scholar 

29. Lynch, J.: Probabilities of first-order sentences about unary functions. Trans. AMS 287 (1985) 543–568

    Google Scholar 

30. Lynch, J.: Probabilities of sentences about very sparse random graphs. Random Struct. Alg. 3 (1992) 33–53

    Google Scholar 

31. Lynch, J.: The quantifier structure of sentences that characterize nondeterministic time complexity. Comput. Complexity 2 (1992) 40–66

    Google Scholar 

32. Lynch, J.: Convergence laws for random words. Australasian J. of Combinatorics 7 (1993) 145–156

    Google Scholar 

33. Lynch, J.: Infinitary logics and very sparse random graphs. Proc. Eighth Ann. IEEE Symp. on Logic in Computer Science (1993) 191–198; J. Symbolic Logic (to appear)

    Google Scholar 

34. Monk, J.: Mathematical Logic. Springer-Verlag, New York (1976)

    Google Scholar 

35. McKenzie, R., Mycielski, J., Thompson, D.: On boolean functions and connected sets. Math. Systems Theory 5 (1971) 259–270

    Google Scholar 

36. Robinson, J.: Definablilty and decision problems in arithmetics. J. Symbolic Logic 14 (1949) 98–114

    Google Scholar 

37. Schwentick, T.: On winning Ehrenfeucht games and monadic NP. Technical Report 3/95, Institut für Informatik, Johannes Gutenberg-Universität Mainz (1995)

    Google Scholar 

38. Shelah, S., Spencer, J.: Zero-one laws for sparse random graphs. J. AMS 1 (1988) 97–115

    Google Scholar 

39. Spencer, J.: Zero-one laws via the Ehrenfeucht game. Discrete Appl. Math. 30 (1991) 235–252

    Google Scholar 

40. Vardi, M.: The complexity of relational query languages. Proc. 14th ACM Symp. on Theory of Computing (1982) 137–146

    Google Scholar 

41. Woods, A.: Counting finite models. J. Symbolic Logic (to appear)

    Google Scholar 

Download references