dblp.uni-trier.dewww.uni-trier.de

Neil Immerman Vis

List of publications from the DBLP Bibliography Server - FAQ
Coauthor Index - Ask others: ACM DL/Guide - CiteSeerX - CSB - MetaPress - Google - Bing - Yahoo
Home Page

*2009
77EEEric 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)
76EETal 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 Logical Methods in Computer Science 5(2): (2009)
75EEPhilipp Weis, Neil Immerman: Structure Theorem and Strict Alternation Hierarchy for FO^2 on Words Logical Methods in Computer Science 5(3): (2009)
2008
74 Siddharth Srivastava, Neil Immerman, Shlomo Zilberstein: Learning Generalized Plans Using Abstract Counting. AAAI 2008: 991-997
73EEDaniel Gyllstrom, Jagrati Agrawal, Yanlei Diao, Neil Immerman: On Supporting Kleene Closure over Event Streams. ICDE 2008: 1391-1393
72EEJagrati Agrawal, Yanlei Diao, Daniel Gyllstrom, Neil Immerman: Efficient pattern matching over event streams. SIGMOD Conference 2008: 147-160
71EERajeev Alur, Marcelo Arenas, Pablo Barceló, Kousha Etessami, Neil Immerman, Leonid Libkin: First-Order and Temporal Logics for Nested Words CoRR abs/0811.0537: (2008)
70EERajeev Alur, Marcelo Arenas, Pablo Barceló, Kousha Etessami, Neil Immerman, Leonid Libkin: First-Order and Temporal Logics for Nested Words. Logical Methods in Computer Science 4(4): (2008)
2007
69EEPhilipp Weis, Neil Immerman: Structure Theorem and Strict Alternation Hierarchy for FO2 on Words. CSL 2007: 343-357
68EERajeev Alur, Marcelo Arenas, Pablo Barceló, Kousha Etessami, Neil Immerman, Leonid Libkin: First-Order and Temporal Logics for Nested Words. LICS 2007: 151-160
67EETal Lev-Ami, Mooly Sagiv, Neil Immerman, Thomas W. Reps: Constructing Specialized Shape Analyses for Uniform Change. VMCAI 2007: 215-233
66EEPhilipp Weis, Neil Immerman: Structure Theorem and Strict Alternation Hierarchy for FO^2 on Words. Electronic Colloquium on Computational Complexity (ECCC) 14(008): (2007)
2006
65EETal Lev-Ami, Neil Immerman, Shmuel Sagiv: Abstraction for Shape Analysis with Fast and Precise Transformers. CAV 2006: 547-561
64EEPhilipp Weis, Neil Immerman: Structure Theorem and Strict Alternation Hierarchy for FO2 on Words. Circuits, Logic, and Games 2006
2005
63EETal 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
62EEEric Allender, Michael Bauland, Neil Immerman, Henning Schnoor, Heribert Vollmer: The Complexity of Satisfiability Problems: Refining Schaefer's Theorem. MFCS 2005: 71-82
61EEDavid 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
60EENeil Immerman, Alexander Moshe Rabinovich, Thomas W. Reps, Shmuel Sagiv, Greta Yorsh: Verification via Structure Simulation. CAV 2004: 281-294
59EENeil 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
58EEEric 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
57EESudarshan Vasudevan, Brian DeCleene, Neil Immerman, James F. Kurose, Donald F. Towsley: Leader Election Algorithms for Wireless Ad Hoc Networks. DISCEX (1) 2003: 261-272
56EEMicah 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
54EEWilliam Hesse, Neil Immerman: Complete Problems for Dynamic Complexity Classes. LICS 2002: 313-
53EESusan Landau, Neil Immerman: Embedding Linkages on an Integer Lattice. Algorithmica 32(3): 423-436 (2002)
52EEDaniel 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
48EEJoseph 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
46EEDaniel 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)
44EENatasha 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
42EENeil Immerman: Descriptive Complexity and Model Checking. FSTTCS 1998: 1-5
1997
41EENeil 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
36EENeil 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)
33EEKousha 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
30EESushant Patnaik, Neil Immerman: Dyn-FO: A Parallel, Dynamic Complexity Class. PODS 1994: 210-221
29EEKousha 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
27EEEric 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
25EENeil 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
10EEJuris 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

Coauthor Index

1Micah Adler [50] [56]
2Jagrati Agrawal [72] [73]
3Natasha Alechina [44]
4Eric Allender [27] [39] [58] [62] [77]
5Rajeev Alur [68] [70] [71]
6Marcelo Arenas [68] [70] [71]
7José L. Balcázar [27] [39]
8Pablo Barceló [68] [70] [71]
9David A. Mix Barrington [23] [28] [47] [51] [61]
10Michael Bauland [58] [62] [77]
11Daniel S. Bernstein [46] [52]
12Jonathan F. Buss [47]
13Jin-yi Cai [21] [26]
14Brian DeCleene [57]
15Yanlei Diao [72] [73]
16Kousha Etessami [29] [33] [35] [45] [68] [70] [71]
17Michael J. Fischer [12] [14]
18Martin Fürer [21] [26]
19Robert Givan [52]
20Yuri Gurevich [32]
21Daniel Gyllstrom [72] [73]
22Joseph Y. Halpern [48]
23Robert Harper [48]
24Juris Hartmanis [1] [7] [9] [10]
25Matthew Hertz [55]
26William Hesse [54]
27Phokion G. Kolaitis [38] [48]
28Dexter Kozen [15] [19]
29James F. Kurose (Jim Kurose) [57]
30Susan Landau [20] [34] [53]
31Clemens Lautemann [51] [61]
32Tal Lev-Ami [63] [65] [67] [76]
33Leonid Libkin [68] [70] [71]
34Stephen R. Mahaney [1] [17]
35J. Antonio Medina [31] [37]
36J. Eliot B. Moss [55]
37Sushant Patnaik [25] [30] [36] [40]
38Alexander Moshe Rabinovich (Alexander Rabinovich) [59] [60]
39Thomas W. Reps [59] [60] [63] [67] [76]
40Shmuel Sagiv (Mooly Sagiv) [59] [60] [63] [65] [67] [76]
41Henning Schnoor [58] [62] [77]
42Nicole Schweikardt [51] [61]
43Vivian Sewelson [7] [9]
44Saharon Shelah [32]
45S. Srivastava [63]
46Siddharth Srivastava [74] [76]
47David W. Stemple [25] [36]
48Howard Straubing [23]
49Denis Thérien [51] [61]
50Donald F. Towsley [57]
51Moshe Y. Vardi [41] [48]
52Sudarshan Vasudevan [57]
53Victor Vianu [48]
54Heribert Vollmer [58] [62] [77]
55Philipp Weis [64] [66] [69] [75]
56Greta Yorsh [59] [60] [63] [76]
57Shlomo Zilberstein [46] [52] [74]

Colors in the list of coauthors

Copyright © Tue Nov 3 08:52:44 2009 by Michael Ley (ley@uni-trier.de)