Selected Publications of Neil Immerman

• Siddharth Srivastava, Neil Immerman, and, Shlomo Zilberstein, Using Abstraction for Generalized Planning, Workshop on Artificial Intelligence Planning and Learning , in conjunction with ICAPS-07 (longer version of this paper).

• Philipp Weis and Neil Immerman, Structure theorem and strict alternation hierarchy for FO² on words, CSL 2007, 343-357.

• Rajeev Alur, Marcelo Arenas, Pablo Barceló, Kousha Etessami, Neil Immerman, and, Leonid Libkin, First-Order and Temporal Logics for Nested Words, LICS 2007, 151-160.

• Tal Lev-Ami, Mooly Sagiv, Neil Immerman, and Tom Reps, Shape Analysis of Uniform Change, VMCAI '07, 215-233.

• Tal Lev-Ami, Neil Immerman, Mooly Sagiv, Abstraction for Shape Analysis with Fast and Precise Transformers, CAV '06, 533 - 546. (Abstract.html)

• Neil Immerman, Guest Column: Progress in Descriptive Complexity, SIGACT NEWS 36(4) (2005), p. 24-35.

• Tal Lev-Ami, Neil Immerman, Tom Reps, Mooly Sagiv, Siddharth Srivastava, and Greta Yorsh, Simulating Reachability using First-Order Logic with Applications to Verification Of Linked Data Structures, CADE '05, 99 - 115. (Abstract.html)

• D.M. Barrington, N. Immerman, Clemens Lautemann, Nicole Schweikardt, and Denis Thérien ``First-Order Expressibility of Languages with Neutral Letters Or: The Crane Beach Conjecture,'' JCSS 70(2) (2005), 101-127. A preliminary version appeared in, LICS '01, 187-196. (Abstract.html)

• E. Allender, Michael Bauland, Neil Immerman, Henning Schnoor, and Heribert Vollmer, "The Complexity of Satisfiability Problems: Refining Schaefer's Theorem", MFCS '05, 71-82. Journal version submitted. (Abstract.html) ( Post's Lattice in Color, diagram by Henning Schnoor)

• Neil Immerman, Alex Rabinovich, Tom Reps, Mooly Sagiv, and Greta Yorsh, The Boundary Between Decidability and Undecidability for Transitive-Closure Logics, CSL '04, 160-174. (Abstract.html)

• Neil Immerman, Computability and Complexity, in Stanford Encyclopedia of Philosophy.

• Neil Immerman, Alex Rabinovich, Tom Reps, Mooly Sagiv, and Greta Yorsh, Verification via Structure Simulation, CAV '04, 281-294. (Abstract.html)

• Micah Adler and N. Immerman, An n! Lower Bound on Formula Size, ACM Transactions on Computational Logic, 4(3) (2003), 296-314. Preliminary version appeared in LICS '01, 197-206. (Abstract.html)

• Bill Hesse and N. Immerman, Complete Problems for Dynamic Complexity Classes, LICS '02, 313-322. (Abstract.html)

• S. Landau and N. Immerman, Embedding Linkages on an Integer Lattice, Algorithmica, 32(3) (2002), 423--436. (Abstract.html)

• D. Bernstein, R. Givan, and N. Immerman, and, S. Zilberstein "The Complexity of Decentralized Control of Markov Decision Processes". Mathematics of Operations Research, 27(4) (2002), 819 - 840. (Abstract.html)

• M. Hertz, and N. Immerman, and, E. Moss, ``Framework for Analyzing Garbage Collection,'' 2nd IFIP Theoretical Computer Science Congress (2002), 230-241. (Abstract.html)

• J. Halpern , R. Harper , N. Immerman, Ph. Kolaitis, M. Vardi, and, V. Vianu, On the Unusual Effectiveness of Logic in Computer Science, Bulletin of Symbolic Logic. 7(2) (2001), 213-236.

• N. Immerman, J. Buss, and D.M. Barrington, Number of Variables Is Equivalent To Space, Journal of Symbolic Logic, 66(3) (2001), 1217 - 1230. (Abstract.html)

• N. Alechina and N. Immerman, Reachability Logic: An Efficient Fragment of Transitive Closure Logic, Logic Journal of the IGPL 8(3) (2000), 325-338. (Abstract.html)

• K. Etessami and N. Immerman, Tree Canonization and Transitive Closure, Information and Computation 157(1,2) (2000), 2 - 24. A preliminary version appeared in IEEE Logic In Computer Science Symp. (1995), 331-341.

• N. Immerman, Progress in Descriptive Complexity, guest column on Computational Complexity, EATCS Bulletin (Feb., 1999). (Abstract.html)

• Descriptive Complexity, N. Immerman, 1999, Graduate Texts in Computer Science, Springer, New York.

• Descriptive Complexity and Finite Models, edited by N. Immerman and Ph. Kolaitis, 1997, American Mathematical Society.

• N. Immerman and M. Vardi, Model Checking and Transitive Closure Logic, CAV'97, 291 - 302. (Abstract.html)

• S. Patnaik and N. Immerman, Dyn-FO: A Parallel, Dynamic Complexity Class, JCSS 55(2) (1997), 199-209. A preliminary version of this paper appeared in PODS (1994).

• D.M. Barrington, N. Immerman, Time, Hardware, and Uniformity, in Complexity Theory Retrospective II, L. Hemaspaandra and A. Selman, editors, 1997, Springer-Verlag, 1-22. A preliminary version of this paper appeared in Ninth IEEE Structure in Complexity Theory Symposium (1994), 176- 185.

• E. Allender, J. Balcázar and N. Immerman, A First-Order Isomorphism Theorem, SIAM J. Computing 26(2) (1997), 557-567. A preliminary version appeared in Tenth Symp. Theoretical Aspects of Computer Science (1993), 163-174.

• J.A. Medina and N. Immerman, A Generalization of Fagin's Theorem, IEEE Logic In Computer Science Symp. (1996), 2 -- 12. (Abstract.html)

• N. Immerman, S. Patnaik and D. Stemple, The Expressiveness of a Family of Finite Set Languages, Theoretical Computer Science, 155(1) (1996), 111-140. A preliminary version appeared in Tenth ACM Symposium on Principles of Database Systems (May, 1991), 37-52.

• N. Immerman, Descriptive Complexity: A Logician's Approach to Computation, Notices of the American Mathematical Society 42(10) (1995), 1127 - 1133.

• N. Immerman and S. Landau, The Complexity of Iterated Multiplication, Information and Computation (116:1) (1995), 103-116.

• K. Etessami and N. Immerman, Reachability and the Power of Local Ordering, Theoretical Computer Science 148(2) (1995), 227-260. A preliminary version of this paper appeared in Eleventh Symp. Theoretical Aspects of Computer Science (1994), 123 - 135.

• Y. Gurevich, N. Immerman and S. Shelah, McColm's Conjecture, IEEE Logic In Computer Science Symp. (1994), 10-19.

• J.A. Medina and N. Immerman, A Syntactic Characterization of NP-Completeness, IEEE Logic In Computer Science Symp. (1994), 241-250.

• S. Landau and N. Immerman, The Similarities (and Differences) between Polynomials and Integers, International Conference on Number Theoretic and Algebraic Methods in Computer Science (1993), 57-59.

• J. Cai, M. Fürer and N. Immerman, An Optimal Lower Bound on the Number of Variables for Graph Identification, Combinatorica 12:4 (1992), 389-410. A preliminary version appeared in 30th IEEE FOCS Symp. (1989), 612-617.

• N. Immerman and E. Lander, Describing Graphs: A First-Order Approach to Graph Canonization, in Complexity Theory Retrospective, Alan Selman, ed., Springer-Verlag (1990), 59-81.

• D.M. Barrington, N. Immerman and H. Straubing, On Uniformity Within NC¹", JCSS 41:3 (1990), 274 - 306. A preliminary version appeared in Third Annual Structure in Complexity Theory Symp. (1988), 47-59.

• N. Immerman, Descriptive and Computational Complexity, in Computational Complexity Theory, ed. J. Hartmanis, Lecture Notes for AMS Short Course on ComputationComplexity Theory, Proc. Symp. in Applied Math. 38, American Mathematical Society (1989), 75-91.

• N. Immerman and D. Kozen, Definability with Bounded Number of Bound Variables, Information and Computation, 83 (1989), 121-139. A preliminary version appeared in IEEE Logic In Computer Science Symp. (1987), 236-244.

• N. Immerman, Expressibility and Parallel Complexity, SIAM J. of Comput. 18 (1989), 625-638.

• N. Immerman, Nondeterministic Space is Closed Under Complementation, SIAM J. Comput. 17, No. 5 (Oct., 1988), 935-938. Also appeared in Third Structure in Complexity Theory Symp. (1988), 112-115.

• N. Immerman, Languages That Capture Complexity Classes, SIAM J. of Computing 16:4 (1987), 760-778. A preliminary version appeared in 15th ACM STOC Symp. (1983), 347-354.

• N. Immerman, Relational Queries Computable in Polynomial Time, Information and Control 68 (1986), 86-104. A preliminary version appeared in 14th ACM STOC Symp. (1982), 147-152.

• Neil Immerman, Upper and Lower Bounds for First Order Expressibility, JCSS 25 (1982), 76-98. A preliminary version appeared in 21st IEEE FOCS Symp. (1980), 74-82.

• N. Immerman, "Number of Quantifiers is Better Than Number of Tape Cells", JCSS 22(3) (1981), 384-406. A preliminary version appeared as, ``Length of Predicate Calculus Formulas as a New Complexity Measure,'' 20th IEEE FOCS Symp. (1979), 337-347. I don't have either of these on line, but here is a tech report version from Cornell, Feb. 1, 1980, that looks pretty close to the journal version.

• Neil Immerman, "First-Order Expressibility as a New Complexity Measure", Ph.D Thesis, Cornell University, 1980, Cornell Computer Science Dept. Tech Report: 80-432.

  ---