Counting Quantifiers, Successor Relations, and Logarithmic Space

E. Allender, J. Balcazar, N. Immerman, A first-order isomorphism theorem, Annual Symposium on Theoretical Aspects of Computer Science, 1993 Ajtai, 1983, Σ11-formulae on finite structures, Ann. Pure Appl. Logic, 24, 1, 10.1016/0168-0072(83)90038-6 Balcazar, 1988, EATCS Monographs on Theoretical Computer Science, I and II Barrington, 1990, On uniformity within NC1, J. Comput. System Sci., 41, 274, 10.1016/0022-0000(90)90022-D Babai, 1988, Arthur-merlin games: A randomized proof system, and a hierarchy of complexity classes, J. Comput. System Sci., 36, 10.1016/0022-0000(88)90028-1 Cai, 1992, An optimal lower bound on the number of variables for graph identification, Combinatorica, 12, 389, 10.1007/BF01305232 Cook, 1987, Problems complete for deterministic logarithmic space, J. Algorithms, 8, 385, 10.1016/0196-6774(87)90018-6 Cook, 1980, Space lower bounds for maze threadability of restricted machines, SIAM J. Comput., 9, 636, 10.1137/0209048 J. Y. Cai, D. Sivakumar, The resolution of a Hartmanis conjecture, Proc, FOCS '95, 362, 371 K. Etessami, N. Immerman, Reachability and the power of local ordering, 11th Symposium on Theoretical Aspects of Computes Science, 123, 135 1994, Theoret. Comput. Sci. K. Etessami, N. Immerman, Tree canonization and transitive closure, 10th Symposium on Logic in Computer Science, 1995 K. Etessami, Counting quantifiers, successor relations, and logarithmic space, 10th Structure in Complexity Theory Conference, 1995, 2, 11 Fagin, 1974, Generalized first-order spectra and polynomial-time recognizable sets, SIAM–AMS Proceedings, 7 Fraı̈ssé, 1954, Sur quelques classifications des systèms de relations, Publ. Sci. Univ. Alger. I, 1, 35 Furst, 1984, Parity, circuits, and the polynomial time hierarchy, J. Math. Systems Theory, 18, 13, 10.1007/BF01744431 J. Hastad, 1986, Almost optimal lower bounds for small depth circuits, Proc. 18th ACM Symposium on Theory of Computing (STOC), 6, 20 L. Hella, Logical hierarchies in PTIME, 7th Symposium on Logic in Computer Science, 1992, 360, 368 Immerman, 1990, Describing graphs: A first-order approach to graph canonization, 59 Immerman, 1995, The complexity of iterated multiplication, Inform. and Comput., 116, 103, 10.1006/inco.1995.1007 Immerman, 1987, Languages that capture complexity classes, SIAM J. Comput., 16, 760, 10.1137/0216051 N. Immerman, 1989, Descriptive and computational complexity, Computational Complexity Theory, J. Hartmanis, Proc. Symp. in Applied Math. 38, 75, 91, American Mathematical Society, Providence, RI Jones, 1975, Space-bounded reducibility among combinatorial problems, J. Comput. System Sci., 11, 10.1016/S0022-0000(75)80050-X L. Libkin, 1994 S. Lindell, 1995, available on-line from [email protected] L. Libkin, L. Wong, New techniques for studying set languages, bag languages, and aggregate functions, PODS, 1994, 155, 166 Mahaney, 1982, Sparse complete sets for np: Solution of a conjecture of Berman and Hartmanis, J. Comput. System Sci., 25, 130, 10.1016/0022-0000(82)90002-2 Nurmonen, 1996, On winning strategies with unary quantifiers, J. Logic and Comput., 10.1093/logcom/6.6.779 Saxena, 1994, Two-coloring a linked list is NC1, Information Processing Letters, 49, 73, 10.1016/0020-0190(94)90030-2 C. K. Poon, Space bounds for graph connectivity problems on node-named JAGs and node-ordered JAGs, IEEE Symposium on Foundations of Computer Science (FOCS), 1993, 218, 227 Straubing, 1994 Valiant, 1982, Reducibility by algebraic projections, L'Enseign. Math., 28, 253