| 2009 |
|---|
| 75 | EE | Tal Lev-Ami,
Neil Immerman,
Thomas W. Reps,
Mooly Sagiv,
Siddharth Srivastava,
Greta Yorsh:
Simulating reachability using first-order logic with applications to verification of linked data structures
CoRR abs/0904.4902: (2009) |
| 74 | EE | Eric Allender,
Michael Bauland,
Neil Immerman,
Henning Schnoor,
Heribert Vollmer:
The complexity of satisfiability problems: Refining Schaefer's theorem.
J. Comput. Syst. Sci. 75(4): 245-254 (2009) |
| 2008 |
|---|
| 73 | | Siddharth Srivastava,
Neil Immerman,
Shlomo Zilberstein:
Learning Generalized Plans Using Abstract Counting.
AAAI 2008: 991-997 |
| 72 | EE | Daniel Gyllstrom,
Jagrati Agrawal,
Yanlei Diao,
Neil Immerman:
On Supporting Kleene Closure over Event Streams.
ICDE 2008: 1391-1393 |
| 71 | EE | Jagrati Agrawal,
Yanlei Diao,
Daniel Gyllstrom,
Neil Immerman:
Efficient pattern matching over event streams.
SIGMOD Conference 2008: 147-160 |
| 70 | EE | Rajeev Alur,
Marcelo Arenas,
Pablo Barceló,
Kousha Etessami,
Neil Immerman,
Leonid Libkin:
First-Order and Temporal Logics for Nested Words
CoRR abs/0811.0537: (2008) |
| 2007 |
|---|
| 69 | EE | Philipp Weis,
Neil Immerman:
Structure Theorem and Strict Alternation Hierarchy for FO2 on Words.
CSL 2007: 343-357 |
| 68 | EE | Rajeev Alur,
Marcelo Arenas,
Pablo Barceló,
Kousha Etessami,
Neil Immerman,
Leonid Libkin:
First-Order and Temporal Logics for Nested Words.
LICS 2007: 151-160 |
| 67 | EE | Tal Lev-Ami,
Mooly Sagiv,
Neil Immerman,
Thomas W. Reps:
Constructing Specialized Shape Analyses for Uniform Change.
VMCAI 2007: 215-233 |
| 66 | EE | Philipp Weis,
Neil Immerman:
Structure Theorem and Strict Alternation Hierarchy for FO^2 on Words.
Electronic Colloquium on Computational Complexity (ECCC) 14(008): (2007) |
| 2006 |
|---|
| 65 | EE | Tal Lev-Ami,
Neil Immerman,
Shmuel Sagiv:
Abstraction for Shape Analysis with Fast and Precise Transformers.
CAV 2006: 547-561 |
| 64 | EE | Philipp Weis,
Neil Immerman:
Structure Theorem and Strict Alternation Hierarchy for FO2 on Words.
Circuits, Logic, and Games 2006 |
| 2005 |
|---|
| 63 | EE | Tal Lev-Ami,
Neil Immerman,
Thomas W. Reps,
Shmuel Sagiv,
S. Srivastava,
Greta Yorsh:
Simulating Reachability Using First-Order Logic with Applications to Verification of Linked Data Structures.
CADE 2005: 99-115 |
| 62 | EE | Eric Allender,
Michael Bauland,
Neil Immerman,
Henning Schnoor,
Heribert Vollmer:
The Complexity of Satisfiability Problems: Refining Schaefer's Theorem.
MFCS 2005: 71-82 |
| 61 | EE | David A. Mix Barrington,
Neil Immerman,
Clemens Lautemann,
Nicole Schweikardt,
Denis Thérien:
First-order expressibility of languages with neutral letters or: The Crane Beach conjecture.
J. Comput. Syst. Sci. 70(2): 101-127 (2005) |
| 2004 |
|---|
| 60 | EE | Neil Immerman,
Alexander Moshe Rabinovich,
Thomas W. Reps,
Shmuel Sagiv,
Greta Yorsh:
Verification via Structure Simulation.
CAV 2004: 281-294 |
| 59 | EE | Neil Immerman,
Alexander Moshe Rabinovich,
Thomas W. Reps,
Shmuel Sagiv,
Greta Yorsh:
The Boundary Between Decidability and Undecidability for Transitive-Closure Logics.
CSL 2004: 160-174 |
| 58 | EE | Eric Allender,
Michael Bauland,
Neil Immerman,
Henning Schnoor,
Heribert Vollmer:
The Complexity of Satisfiability Problems: Refining Schaefer's Theorem
Electronic Colloquium on Computational Complexity (ECCC)(100): (2004) |
| 2003 |
|---|
| 57 | EE | Sudarshan Vasudevan,
Brian DeCleene,
Neil Immerman,
James F. Kurose,
Donald F. Towsley:
Leader Election Algorithms for Wireless Ad Hoc Networks.
DISCEX (1) 2003: 261-272 |
| 56 | EE | Micah Adler,
Neil Immerman:
An n! lower bound on formula size.
ACM Trans. Comput. Log. 4(3): 296-314 (2003) |
| 2002 |
|---|
| 55 | | Matthew Hertz,
Neil Immerman,
J. Eliot B. Moss:
Framework for Analyzing Garbage Collection.
IFIP TCS 2002: 230-242 |
| 54 | EE | William Hesse,
Neil Immerman:
Complete Problems for Dynamic Complexity Classes.
LICS 2002: 313- |
| 53 | EE | Susan Landau,
Neil Immerman:
Embedding Linkages on an Integer Lattice.
Algorithmica 32(3): 423-436 (2002) |
| 52 | EE | Daniel S. Bernstein,
Robert Givan,
Neil Immerman,
Shlomo Zilberstein:
The Complexity of Decentralized Control of Markov Decision Processes.
Math. Oper. Res. 27(4): 819-840 (2002) |
| 2001 |
|---|
| 51 | | David A. Mix Barrington,
Neil Immerman,
Clemens Lautemann,
Nicole Schweikardt,
Denis Thérien:
The Crane Beach Conjecture.
LICS 2001: 187-196 |
| 50 | | Micah Adler,
Neil Immerman:
An n! Lower Bound on Formula Size.
LICS 2001: 197- |
| 49 | | Neil Immerman:
Progress in Descriptive Complexity.
Current Trends in Theoretical Computer Science 2001: 71-82 |
| 48 | EE | Joseph Y. Halpern,
Robert Harper,
Neil Immerman,
Phokion G. Kolaitis,
Moshe Y. Vardi,
Victor Vianu:
On the unusual effectiveness of logic in computer science.
Bulletin of Symbolic Logic 7(2): 213-236 (2001) |
| 47 | | Neil Immerman,
Jonathan F. Buss,
David A. Mix Barrington:
Number of Variables Is Equivalent to Space.
J. Symb. Log. 66(3): 1217-1230 (2001) |
| 2000 |
|---|
| 46 | EE | Daniel S. Bernstein,
Shlomo Zilberstein,
Neil Immerman:
The Complexity of Decentralized Control of Markov Decision Processes.
UAI 2000: 32-37 |
| 45 | | Kousha Etessami,
Neil Immerman:
Tree Canonization and Transitive Closure.
Inf. Comput. 157(1-2): 2-24 (2000) |
| 44 | EE | Natasha Alechina,
Neil Immerman:
Reachability Logic: An Efficient Fragment of Transitive Closure Logic.
Logic Journal of the IGPL 8(3): (2000) |
| 1999 |
|---|
| 43 | | Neil Immerman:
Progress in Descriptive Complexity.
Bulletin of the EATCS 67: 72-81 (1999) |
| 1998 |
|---|
| 42 | | Neil Immerman:
Descriptive Complexity and Model Checking.
FSTTCS 1998: 1-5 |
| 1997 |
|---|
| 41 | | Neil Immerman,
Moshe Y. Vardi:
Model Checking and Transitive-Closure Logic.
CAV 1997: 291-302 |
| 40 | | Sushant Patnaik,
Neil Immerman:
Dyn-FO: A Parallel, Dynamic Complexity Class.
J. Comput. Syst. Sci. 55(2): 199-209 (1997) |
| 39 | | Eric Allender,
José L. Balcázar,
Neil Immerman:
A First-Order Isomorphism Theorem.
SIAM J. Comput. 26(2): 557-567 (1997) |
| 1996 |
|---|
| 38 | | Neil Immerman,
Phokion G. Kolaitis:
Descriptive Complexity and Finite Models, Proceedings of a DIMACS Workshop, January 14-17, 1996, Princeton University
American Mathematical Society 1996 |
| 37 | | J. Antonio Medina,
Neil Immerman:
A Generalization of Fagin's Theorem.
LICS 1996: 2-12 |
| 36 | EE | Neil Immerman,
Sushant Patnaik,
David W. Stemple:
The Expressiveness of a Family of Finite Set Languages.
Theor. Comput. Sci. 155(1): 111-140 (1996) |
| 1995 |
|---|
| 35 | | Kousha Etessami,
Neil Immerman:
Tree Canonization and Transitive Closure
LICS 1995: 331-341 |
| 34 | | Neil Immerman,
Susan Landau:
The Complexity of Iterated Multiplication
Inf. Comput. 116(1): 103-116 (1995) |
| 33 | EE | Kousha Etessami,
Neil Immerman:
Reachability and the Power of Local Ordering.
Theor. Comput. Sci. 148(2): 261-279 (1995) |
| 1994 |
|---|
| 32 | | Yuri Gurevich,
Neil Immerman,
Saharon Shelah:
McColm's Conjecture
LICS 1994: 10-19 |
| 31 | | J. Antonio Medina,
Neil Immerman:
A Syntactic Characterization of NP-Completeness
LICS 1994: 241-250 |
| 30 | EE | Sushant Patnaik,
Neil Immerman:
Dyn-FO: A Parallel, Dynamic Complexity Class.
PODS 1994: 210-221 |
| 29 | | Kousha Etessami,
Neil Immerman:
Reachability and the Power of Local Ordering.
STACS 1994: 123-135 |
| 28 | | David A. Mix Barrington,
Neil Immerman:
Time, Hardware, and Uniformity.
Structure in Complexity Theory Conference 1994: 176-185 |
| 1993 |
|---|
| 27 | | Eric Allender,
José L. Balcázar,
Neil Immerman:
A First-Order Isomorphism Theorem.
STACS 1993: 163-174 |
| 1992 |
|---|
| 26 | | Jin-yi Cai,
Martin Fürer,
Neil Immerman:
An optimal lower bound on the number of variables for graph identifications.
Combinatorica 12(4): 389-410 (1992) |
| 1991 |
|---|
| 25 | EE | Neil Immerman,
Sushant Patnaik,
David W. Stemple:
The Expressiveness of a Family of Finite Set Languages.
PODS 1991: 37-52 |
| 24 | | Neil Immerman:
DSPACE[nk] = VAR[k+1].
Structure in Complexity Theory Conference 1991: 334-340 |
| 1990 |
|---|
| 23 | | David A. Mix Barrington,
Neil Immerman,
Howard Straubing:
On Uniformity within NC¹.
J. Comput. Syst. Sci. 41(3): 274-306 (1990) |
| 1989 |
|---|
| 22 | | Neil Immerman:
Descriptive and Computational Complexity.
FCT 1989: 244-245 |
| 21 | | Jin-yi Cai,
Martin Fürer,
Neil Immerman:
An Optimal Lower Bound on the Number of Variables for Graph Identification
FOCS 1989: 612-617 |
| 20 | | Neil Immerman,
Susan Landau:
The Complexity of Iterated Multiplication.
Structure in Complexity Theory Conference 1989: 104-111 |
| 19 | | Neil Immerman,
Dexter Kozen:
Definability with Bounded Number of Bound Variables
Inf. Comput. 83(2): 121-139 (1989) |
| 18 | | Neil Immerman:
Expressibility and Parallel Complexity.
SIAM J. Comput. 18(3): 625-638 (1989) |
| 17 | | Neil Immerman,
Stephen R. Mahaney:
Relativizing Relativized Computations.
Theor. Comput. Sci. 68(3): 267-276 (1989) |
| 1988 |
|---|
| 16 | | Neil Immerman:
Nondeterministic Space is Closed Under Complementation.
SIAM J. Comput. 17(5): 935-938 (1988) |
| 1987 |
|---|
| 15 | | Neil Immerman,
Dexter Kozen:
Definability with Bounded Number of Bound Variables
LICS 1987: 236-244 |
| 14 | | Michael J. Fischer,
Neil Immerman:
Interpreting Logics of Knowledge in Propositional Dynamic Logic with Converse.
Inf. Process. Lett. 25(3): 175-181 (1987) |
| 13 | | Neil Immerman:
Languages that Capture Complexity Classes.
SIAM J. Comput. 16(4): 760-778 (1987) |
| 1986 |
|---|
| 12 | | Michael J. Fischer,
Neil Immerman:
Foundations of Knowledge for Distributed Systems.
TARK 1986: 171-185 |
| 11 | | Neil Immerman:
Relational Queries Computable in Polynomial Time
Information and Control 68(1-3): 86-104 (1986) |
| 1985 |
|---|
| 10 | | Juris Hartmanis,
Neil Immerman:
On Complete Problems for NP$\cap$CoNP.
ICALP 1985: 250-259 |
| 9 | | Juris Hartmanis,
Neil Immerman,
Vivian Sewelson:
Sparse Sets in NP-P: EXPTIME versus NEXPTIME
Information and Control 65(2/3): 158-181 (1985) |
| 1983 |
|---|
| 8 | | Neil Immerman:
Languages Which Capture Complexity Classes (Preliminary Report)
STOC 1983: 347-354 |
| 7 | | Juris Hartmanis,
Vivian Sewelson,
Neil Immerman:
Sparse Sets in NP-P: EXPTIME versus NEXPTIME
STOC 1983: 382-391 |
| 1982 |
|---|
| 6 | | Neil Immerman:
Relational Queries Computable in Polynomial Time (Extended Abstract)
STOC 1982: 147-152 |
| 5 | | Neil Immerman:
Upper and Lower Bounds for First Order Expressibility.
J. Comput. Syst. Sci. 25(1): 76-98 (1982) |
| 1981 |
|---|
| 4 | | Neil Immerman:
Number of Quantifiers is Better Than Number of Tape Cells.
J. Comput. Syst. Sci. 22(3): 384-406 (1981) |
| 1980 |
|---|
| 3 | | Neil Immerman:
Upper and Lower Bounds for First Order Expressibility
FOCS 1980: 74-82 |
| 1979 |
|---|
| 2 | | Neil Immerman:
Length of Predicate Calculus Formulas as a New Complexity Measure
FOCS 1979: 337-347 |
| 1978 |
|---|
| 1 | | Juris Hartmanis,
Neil Immerman,
Stephen R. Mahaney:
One-Way Log-Tape Reductions
FOCS 1978: 65-72 |
