Publications with Y. Gurevich

All publications by Yuri Gurevich and S. Shelah

Click the Sh:-number to get to the papers' detail page (which may include pdf's of the paper).
Can't find an Sh:-number (in particular, an "F-number")? You can try your luck here.
number title
Sh:70 Gurevich, Y., & Shelah, S. (1979). Modest theory of short chains. II. J. Symbolic Logic, 44(4), 491–502. DOI: 10.2307/2273288 MR: 550378
Sh:123 Gurevich, Y., & Shelah, S. (1982). Monadic theory of order and topology in ZFC. Ann. Math. Logic, 23(2-3), 179–198 (1983). DOI: 10.1016/0003-4843(82)90004-3 MR: 701125
Sh:135 Glass, A. M. W., Gurevich, Y., Holland, W. C., & Shelah, S. (1981). Rigid homogeneous chains. Math. Proc. Cambridge Philos. Soc., 89(1), 7–17. DOI: 10.1017/S0305004100057881 MR: 591966
Sh:141 Gurevich, Y., Magidor, M., & Shelah, S. (1983). The monadic theory of \omega_2. J. Symbolic Logic, 48(2), 387–398. DOI: 10.2307/2273556 MR: 704093
Sh:143 Gurevich, Y., & Shelah, S. (1984). The monadic theory and the “next world”. Israel J. Math., 49(1-3), 55–68. DOI: 10.1007/BF02760646 MR: 788265
Sh:151 Gurevich, Y., & Shelah, S. (1983). Interpreting second-order logic in the monadic theory of order. J. Symbolic Logic, 48(3), 816–828. DOI: 10.2307/2273475 MR: 716644
Sh:163 Gurevich, Y., & Shelah, S. (1985). To the decision problem for branching time logic. In Foundations of logic and linguistics (Salzburg, 1983), Plenum, New York, pp. 181–198. MR: 797952
Sh:168 Gurevich, Y., & Shelah, S. (1989). On the strength of the interpretation method. J. Symbolic Logic, 54(2), 305–323. DOI: 10.2307/2274850 MR: 997869
Sh:178 Gurevich, Y., & Shelah, S. (1983). Random models and the Gödel case of the decision problem. J. Symbolic Logic, 48(4), 1120–1124 (1984). DOI: 10.2307/2273674 MR: 727799
Sh:183 Gurevich, Y., & Shelah, S. (1983). Rabin’s uniformization problem. J. Symbolic Logic, 48(4), 1105–1119 (1984). DOI: 10.2307/2273673 MR: 727798
Sh:184 Goldfarb, W. D., Gurevich, Y., & Shelah, S. (1984). A decidable subclass of the minimal Gödel class with identity. J. Symbolic Logic, 49(4), 1253–1261. DOI: 10.2307/2274275 MR: 771791
Sh:213 Denenberg, L., Gurevich, Y., & Shelah, S. (1986). Definability by constant-depth polynomial-size circuits. Inform. And Control, 70(2-3), 216–240. DOI: 10.1016/S0019-9958(86)80006-7 MR: 859107
Sh:230 Gurevich, Y., & Shelah, S. (1985). The decision problem for branching time logic. J. Symbolic Logic, 50(3), 668–681. DOI: 10.2307/2274321 MR: 805676
Sh:243 Gurevich, Y., & Shelah, S. (1987). Expected computation time for Hamiltonian path problem. SIAM J. Comput., 16(3), 486–502. DOI: 10.1137/0216034 MR: 889404
Sh:244 Gurevich, Y., & Shelah, S. (1985). Fixed-point extensions of first-order logic. In 26th Annual Symposium on Foundations of Computer Science (sfcs 1985), IEEE Computer Science Society Press, pp. 346–353. DOI: 10.1109/SFCF.1985.27
Conference proceedings version of [Sh:244a]
Sh:244a Gurevich, Y., & Shelah, S. (1986). Fixed-point extensions of first-order logic. Ann. Pure Appl. Logic, 32(3), 265–280. DOI: 10.1016/0168-0072(86)90055-2 MR: 865992
See [Sh:244]
Sh:277 Gurevich, Y., & Shelah, S. (1989). Nearly linear time. In Logic at Botik ’89 (Pereslavl-Zalesskiy, 1989), Vol. 363, Springer, Berlin, pp. 108–118. DOI: 10.1007/3-540-51237-3_10 MR: 1030571
Sh:332 Gurevich, Y., & Shelah, S. (1988). Nondeterministic Linear Tasks May Require Substantially Nonlinear Deterministic Time in the Case of Sublinear Work Space. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, New York, NY, USA: ACM, pp. 281–289. DOI: 10.1145/62212.62239
Sh:332a Gurevich, Y., & Shelah, S. (1990). Nondeterministic linear-time tasks may require substantially nonlinear deterministic time in the case of sublinear work space. J. Assoc. Comput. Mach., 37(3), 674–687. DOI: 10.1145/79147.214070 MR: 1072274
Sh:343 Gurevich, Y., & Shelah, S. (1989). Time polynomial in input or output. J. Symbolic Logic, 54(3), 1083–1088. DOI: 10.2307/2274767 MR: 1011194
Sh:525 Gurevich, Y., Immerman, N., & Shelah, S. (1994). McColm’s conjecture [positive elementary inductions]. In Proceedings Ninth Annual IEEE Symposium on Logic in Computer Science, IEEE Computer Society Press, pp. 10–19. arXiv: math/9411235 DOI: 10.1109/LICS.1994.316091
Sh:526 Gurevich, Y., & Shelah, S. (1996). On finite rigid structures. J. Symbolic Logic, 61(2), 549–562. arXiv: math/9411236 DOI: 10.2307/2275675 MR: 1394614
Sh:533 Blass, A. R., Gurevich, Y., & Shelah, S. (1999). Choiceless polynomial time. Ann. Pure Appl. Logic, 100(1-3), 141–187. arXiv: math/9705225 DOI: 10.1016/S0168-0072(99)00005-6 MR: 1711992
See [Sh:533a]
Sh:533a Blass, A. R., Gurevich, Y., & Shelah, S. (2001). Addendum to: “Choiceless polynomial time” [Ann. Pure Appl. Logic 100 (1999), no. 1-3, 141–187;MR1711992 (2001a:68036)]. Ann. Pure Appl. Logic, 112(1), 117. DOI: 10.1016/S0168-0072(01)00086-0 MR: 1854233
Correction of [Sh:533]
Sh:536 Gurevich, Y., & Shelah, S. (2003). Spectra of Monadic Second-Order Formulas with One Unary Function. In 18th Annual IEEE Symposium of Logic in Computer Science, 2003. Proceedings., pp. 291–300. arXiv: math/0404150 DOI: 10.1109/LICS.2003.1210069
Sh:760 Blass, A. R., Gurevich, Y., & Shelah, S. (2002). On polynomial time computation over unordered structures. J. Symbolic Logic, 67(3), 1093–1125. arXiv: math/0102059 DOI: 10.2178/jsl/1190150152 MR: 1926601