Selected Publications of Neil Immerman

• Siddharth Srivastava, Neil Immerman, Shlomo Zilberstein, Applicability Conditions for Plans with Loops: Computability Results and Algorithms Artificial Intelligence, 191–192 (2012), 1–19.

• Wentian Lu, Gerome Miklau, and Neil Immerman, Auditing a Database Under Retention Policies, VLDB Journal (July, 2012).

• Christoph Reichenbach, Yannis Smaragdakis, and Neil Immerman, PQL: A Purely-Declarative Java Extension for Parallel Programming, ECOOP 2012.

• Marco Carmosino, Neil Immerman and Charles Jordan, Experimental Descriptive Complexity, Logic and Program Semantics: Essays Dedicated to Dexter Kozen on the Occasion of His 60th Birthday 2012, R.L. Constable and A. Silva, eds., Springer LNCS 7230, 24-34.

• Siddharth Srivastava, Neil Immerman, Shlomo Zilberstein, A New Representation and Associated Algorithms for Generalized Planning, Artificial Intelligence, 175(2), (Feb. 2011), 615-647.

• A Simple Inductive Synthesis Methodology and its Applications, Shachar Itzhaky, Sumit Gulwani, Neil Immerman and Mooly Sagiv, OOPSLA '10 Proceedings of the ACM International Conference on Object Oriented Programming Systems Languages and Applications, 2010

• What can the GC compute efficiently?: a language for heap assertions at GC time

  Christoph Reichenbach, Neil Immerman, Yannis Smaragdakis, Edward E. Aftandilian, Samuel Z. Guyer
  OOPSLA '10 Proceedings of the ACM international conference on Object oriented programming systems languages and applications, 2010

• Haopeng Zhang, Yanlei Diao, and Neil Immerman, Recognizing Patterns in Streams with Imprecise Timestamps, VLDB 2010, 244 - 255.

• Michael Crouch, Neil Immerman, and J. Eliot B. Moss, Finding Reductions Automatically, in Fields of Logic and Computation: Essays Dedicated to Yuri Gurevich on the Occasion of His 70th Birthday, A. Blass, N. Dershowitz, and W. Reisig, eds., (2010), Springer, 181 - 200.

• Siddharth Srivastava, Neil Immerman, Shlomo Zilberstein, Computing Applicability Conditions for Plans with Loops, ICAPS 2010, 161- 168 (Best Paper Award).

• Siddharth Srivastava, Neil Immerman, Shlomo Zilberstein, Merging Example Plans into Generalized Plans for Non-deterministic Environments, Proceedings of the Ninth International Conference on Autonomous Agents and Multiagent Systems (AAMAS) (2010), 1341-1348, Toronto, Canada.

• Philipp Weis and Neil Immerman, Structure theorem and strict alternation hierarchy for FO² on words, Logical Methods in Computer Science 5(3), paper 4 (2009). A prelimiary version appeared in CSL 2007, 343-357.

• 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, Logical Methods in Computer Science 5(2), paper 12 (2009). A preliminary version appeared in CADE '05, 99 - 115. (Abstract.html)

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

• Rajeev Alur, Marcelo Arenas, Pablo Barceló, Kousha Etessami, Neil Immerman, and, Leonid Libkin, First-Order and Temporal Logics for Nested Words, Logical Methods in Computer Science, 4(4), Paper 11, (2008), 1-44. Preliminary version appeared in LICS 2007, 151-160.

• Siddharth Srivastava, Neil Immerman, Shlomo Zilberstein, Learning Generalized Plans Using Abstract Counting, AAAI 2008, 991-997.

• Efficient pattern matching over event streams

  Jagrati Agrawal, Yanlei Diao, Daniel Gyllstrom, Neil Immerman
  SIGMOD '08 Proceedings of the 2008 ACM SIGMOD international conference on Management of data, 2008

• Daniel Gyllstrom, Jagrati Agrawal, Yanlei Diao, and Neil Immerman, On Supporting Kleene Closure over Event Streams, ICDE 2008, 1391-1393.

• 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).

• Tal Lev-Ami, Mooly Sagiv, Neil Immerman, and Tom Reps, Constructing Specialized Shape Analysis for 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.

• 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)

• 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)

• An n! lower bound on formula size

  Micah Adler, Neil Immerman
  ACM Transactions on Computational Logic (TOCL), 2003
  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)

• Susan 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):
  Dyn-FO (preliminary version): a parallel, dynamic complexity class

  Sushant Patnaik, Neil Immerman
  PODS '94 Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, 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 Susan 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.

• Susan 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:
  Relational queries computable in polynomial time (Extended Abstract)

  Neil Immerman
  STOC '82 Proceedings of the fourteenth annual ACM symposium on Theory of computing, 1982

• Sparse sets in NP-P: Exptime versus nexptime

  J. Hartmanis, V. Sewelson, N. Immerman
  STOC '83 Proceedings of the fifteenth annual ACM symposium on Theory of computing, 1983

• 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 the journal version 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.

• Juris Hartmanis, Neil Immerman and Stephen Mahaney, "One-Way Log-tape Reductions", 19th IEEE FOCS Symp. (1978), 65-72.