The SCEAS System
| |||||||

## Search the dblp DataBase
Neil Immerman:
[Publications]
[Author Rank by year]
[Co-authors]
[Prefers]
[Cites]
[Cited by]
## Publications of Author- Neil Immerman
**Relational Queries Computable in Polynomial Time**[Citation Graph (48, 0)][DBLP] Information and Control, 1986, v:68, n:1-3, pp:86-104 [Journal] - Neil Immerman
**Languages that Capture Complexity Classes.**[Citation Graph (26, 0)][DBLP] SIAM J. Comput., 1987, v:16, n:4, pp:760-778 [Journal] - Neil Immerman, Sushant Patnaik, David W. Stemple
**The Expressiveness of a Family of Finite Set Languages.**[Citation Graph (17, 31)][DBLP] PODS, 1991, pp:37-52 [Conf] - Neil Immerman
**Relational Queries Computable in Polynomial Time (Extended Abstract)**[Citation Graph (14, 0)][DBLP] STOC, 1982, pp:147-152 [Conf] - David A. Mix Barrington, Neil Immerman, Howard Straubing
**On Uniformity within NC¹.**[Citation Graph (12, 0)][DBLP] J. Comput. Syst. Sci., 1990, v:41, n:3, pp:274-306 [Journal] - Sushant Patnaik, Neil Immerman
**Dyn-FO: A Parallel, Dynamic Complexity Class.**[Citation Graph (9, 20)][DBLP] PODS, 1994, pp:210-221 [Conf] - Neil Immerman
**Upper and Lower Bounds for First Order Expressibility.**[Citation Graph (8, 0)][DBLP] J. Comput. Syst. Sci., 1982, v:25, n:1, pp:76-98 [Journal] - Neil Immerman
**Number of Quantifiers is Better Than Number of Tape Cells.**[Citation Graph (7, 0)][DBLP] J. Comput. Syst. Sci., 1981, v:22, n:3, pp:384-406 [Journal] - Neil Immerman
**Expressibility and Parallel Complexity.**[Citation Graph (6, 0)][DBLP] SIAM J. Comput., 1989, v:18, n:3, pp:625-638 [Journal] - Jin-yi Cai, Martin Fürer, Neil Immerman
**An Optimal Lower Bound on the Number of Variables for Graph Identification**[Citation Graph (5, 0)][DBLP] FOCS, 1989, pp:612-617 [Conf] - Neil Immerman, Dexter Kozen
**Definability with Bounded Number of Bound Variables**[Citation Graph (4, 0)][DBLP] Inf. Comput., 1989, v:83, n:2, pp:121-139 [Journal] - Sushant Patnaik, Neil Immerman
**Dyn-FO: A Parallel, Dynamic Complexity Class.**[Citation Graph (4, 0)][DBLP] J. Comput. Syst. Sci., 1997, v:55, n:2, pp:199-209 [Journal] - Kousha Etessami, Neil Immerman
**Tree Canonization and Transitive Closure**[Citation Graph (3, 0)][DBLP] LICS, 1995, pp:331-341 [Conf] - Neil Immerman
**Languages Which Capture Complexity Classes (Preliminary Report)**[Citation Graph (3, 0)][DBLP] STOC, 1983, pp:347-354 [Conf] - Neil Immerman
**Nondeterministic Space is Closed Under Complementation.**[Citation Graph (3, 0)][DBLP] SIAM J. Comput., 1988, v:17, n:5, pp:935-938 [Journal] - Neil Immerman, Susan Landau
**The Complexity of Iterated Multiplication**[Citation Graph (2, 0)][DBLP] Inf. Comput., 1995, v:116, n:1, pp:103-116 [Journal] - Neil Immerman, Moshe Y. Vardi
**Model Checking and Transitive-Closure Logic.**[Citation Graph (1, 0)][DBLP] CAV, 1997, pp:291-302 [Conf] - Neil Immerman
**Length of Predicate Calculus Formulas as a New Complexity Measure**[Citation Graph (1, 0)][DBLP] FOCS, 1979, pp:337-347 [Conf] - Juris Hartmanis, Neil Immerman, Vivian Sewelson
**Sparse Sets in NP-P: EXPTIME versus NEXPTIME**[Citation Graph (1, 0)][DBLP] Information and Control, 1985, v:65, n:2/3, pp:158-181 [Journal] - 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.**[Citation Graph (0, 0)][DBLP] CADE, 2005, pp:99-115 [Conf] - Neil Immerman, Alexander Moshe Rabinovich, Thomas W. Reps, Shmuel Sagiv, Greta Yorsh
**Verification via Structure Simulation.**[Citation Graph (0, 0)][DBLP] CAV, 2004, pp:281-294 [Conf] - Tal Lev-Ami, Neil Immerman, Shmuel Sagiv
**Abstraction for Shape Analysis with Fast and Precise Transformers.**[Citation Graph (0, 0)][DBLP] CAV, 2006, pp:547-561 [Conf] - David A. Mix Barrington, Neil Immerman
**Time, Hardware, and Uniformity.**[Citation Graph (0, 0)][DBLP] Structure in Complexity Theory Conference, 1994, pp:176-185 [Conf] - Neil Immerman
**DSPACE[n**[Citation Graph (0, 0)][DBLP]^{k}] = VAR[k+1]. Structure in Complexity Theory Conference, 1991, pp:334-340 [Conf] - Neil Immerman, Susan Landau
**The Complexity of Iterated Multiplication.**[Citation Graph (0, 0)][DBLP] Structure in Complexity Theory Conference, 1989, pp:104-111 [Conf] - Neil Immerman, Alexander Moshe Rabinovich, Thomas W. Reps, Shmuel Sagiv, Greta Yorsh
**The Boundary Between Decidability and Undecidability for Transitive-Closure Logics.**[Citation Graph (0, 0)][DBLP] CSL, 2004, pp:160-174 [Conf] - Sudarshan Vasudevan, Brian DeCleene, Neil Immerman, James F. Kurose, Donald F. Towsley
**Leader Election Algorithms for Wireless Ad Hoc Networks.**[Citation Graph (0, 0)][DBLP] DISCEX (1), 2003, pp:261-272 [Conf] - Neil Immerman
**Descriptive and Computational Complexity.**[Citation Graph (0, 0)][DBLP] FCT, 1989, pp:244-245 [Conf] - Juris Hartmanis, Neil Immerman, Stephen R. Mahaney
**One-Way Log-Tape Reductions**[Citation Graph (0, 0)][DBLP] FOCS, 1978, pp:65-72 [Conf] - Neil Immerman
**Upper and Lower Bounds for First Order Expressibility**[Citation Graph (0, 0)][DBLP] FOCS, 1980, pp:74-82 [Conf] - Neil Immerman
**Descriptive Complexity and Model Checking.**[Citation Graph (0, 0)][DBLP] FSTTCS, 1998, pp:1-5 [Conf] - Juris Hartmanis, Neil Immerman
**On Complete Problems for NP$\cap$CoNP.**[Citation Graph (0, 0)][DBLP] ICALP, 1985, pp:250-259 [Conf] - Matthew Hertz, Neil Immerman, J. Eliot B. Moss
**Framework for Analyzing Garbage Collection.**[Citation Graph (0, 0)][DBLP] IFIP TCS, 2002, pp:230-242 [Conf] - David A. Mix Barrington, Neil Immerman, Clemens Lautemann, Nicole Schweikardt, Denis Thérien
**The Crane Beach Conjecture.**[Citation Graph (0, 0)][DBLP] LICS, 2001, pp:187-196 [Conf] - Micah Adler, Neil Immerman
**An n! Lower Bound on Formula Size.**[Citation Graph (0, 0)][DBLP] LICS, 2001, pp:197-0 [Conf] - Yuri Gurevich, Neil Immerman, Saharon Shelah
**McColm's Conjecture**[Citation Graph (0, 0)][DBLP] LICS, 1994, pp:10-19 [Conf] - William Hesse, Neil Immerman
**Complete Problems for Dynamic Complexity Classes.**[Citation Graph (0, 0)][DBLP] LICS, 2002, pp:313-0 [Conf] - Neil Immerman, Dexter Kozen
**Definability with Bounded Number of Bound Variables**[Citation Graph (0, 0)][DBLP] LICS, 1987, pp:236-244 [Conf] - J. Antonio Medina, Neil Immerman
**A Syntactic Characterization of NP-Completeness**[Citation Graph (0, 0)][DBLP] LICS, 1994, pp:241-250 [Conf] - J. Antonio Medina, Neil Immerman
**A Generalization of Fagin's Theorem.**[Citation Graph (0, 0)][DBLP] LICS, 1996, pp:2-12 [Conf] - Eric Allender, Michael Bauland, Neil Immerman, Henning Schnoor, Heribert Vollmer
**The Complexity of Satisfiability Problems: Refining Schaefer's Theorem.**[Citation Graph (0, 0)][DBLP] MFCS, 2005, pp:71-82 [Conf] - Eric Allender, José L. Balcázar, Neil Immerman
**A First-Order Isomorphism Theorem.**[Citation Graph (0, 0)][DBLP] STACS, 1993, pp:163-174 [Conf] - Kousha Etessami, Neil Immerman
**Reachability and the Power of Local Ordering.**[Citation Graph (0, 0)][DBLP] STACS, 1994, pp:123-135 [Conf] - Juris Hartmanis, Vivian Sewelson, Neil Immerman
**Sparse Sets in NP-P: EXPTIME versus NEXPTIME**[Citation Graph (0, 0)][DBLP] STOC, 1983, pp:382-391 [Conf] - Michael J. Fischer, Neil Immerman
**Foundations of Knowledge for Distributed Systems.**[Citation Graph (0, 0)][DBLP] TARK, 1986, pp:171-185 [Conf] - Daniel S. Bernstein, Shlomo Zilberstein, Neil Immerman
**The Complexity of Decentralized Control of Markov Decision Processes.**[Citation Graph (0, 0)][DBLP] UAI, 2000, pp:32-37 [Conf] - Susan Landau, Neil Immerman
**Embedding Linkages on an Integer Lattice.**[Citation Graph (0, 0)][DBLP] Algorithmica, 2002, v:32, n:3, pp:423-436 [Journal] - Joseph Y. Halpern, Robert Harper, Neil Immerman, Phokion G. Kolaitis, Moshe Y. Vardi, Victor Vianu
**On the unusual effectiveness of logic in computer science.**[Citation Graph (0, 0)][DBLP] Bulletin of Symbolic Logic, 2001, v:7, n:2, pp:213-236 [Journal] - Jin-yi Cai, Martin Fürer, Neil Immerman
**An optimal lower bound on the number of variables for graph identifications.**[Citation Graph (0, 0)][DBLP] Combinatorica, 1992, v:12, n:4, pp:389-410 [Journal] - Neil Immerman
**Progress in Descriptive Complexity.**[Citation Graph (0, 0)][DBLP] Bulletin of the EATCS, 1999, v:67, n:, pp:72-81 [Journal] - Eric Allender, Michael Bauland, Neil Immerman, Henning Schnoor, Heribert Vollmer
**The Complexity of Satisfiability Problems: Refining Schaefer's Theorem**[Citation Graph (0, 0)][DBLP] Electronic Colloquium on Computational Complexity (ECCC), 2004, v:, n:100, pp:- [Journal] - Kousha Etessami, Neil Immerman
**Tree Canonization and Transitive Closure.**[Citation Graph (0, 0)][DBLP] Inf. Comput., 2000, v:157, n:1-2, pp:2-24 [Journal] - Natasha Alechina, Neil Immerman
**Reachability Logic: An Efficient Fragment of Transitive Closure Logic.**[Citation Graph (0, 0)][DBLP] Logic Journal of the IGPL, 2000, v:8, n:3, pp:- [Journal] - Michael J. Fischer, Neil Immerman
**Interpreting Logics of Knowledge in Propositional Dynamic Logic with Converse.**[Citation Graph (0, 0)][DBLP] Inf. Process. Lett., 1987, v:25, n:3, pp:175-181 [Journal] - 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.**[Citation Graph (0, 0)][DBLP] J. Comput. Syst. Sci., 2005, v:70, n:2, pp:101-127 [Journal] - Neil Immerman, Jonathan F. Buss, David A. Mix Barrington
**Number of Variables Is Equivalent to Space.**[Citation Graph (0, 0)][DBLP] J. Symb. Log., 2001, v:66, n:3, pp:1217-1230 [Journal] - Daniel S. Bernstein, Robert Givan, Neil Immerman, Shlomo Zilberstein
**The Complexity of Decentralized Control of Markov Decision Processes.**[Citation Graph (0, 0)][DBLP] Math. Oper. Res., 2002, v:27, n:4, pp:819-840 [Journal] - Eric Allender, José L. Balcázar, Neil Immerman
**A First-Order Isomorphism Theorem.**[Citation Graph (0, 0)][DBLP] SIAM J. Comput., 1997, v:26, n:2, pp:557-567 [Journal] - Kousha Etessami, Neil Immerman
**Reachability and the Power of Local Ordering.**[Citation Graph (0, 0)][DBLP] Theor. Comput. Sci., 1995, v:148, n:2, pp:261-279 [Journal] - Neil Immerman, Stephen R. Mahaney
**Relativizing Relativized Computations.**[Citation Graph (0, 0)][DBLP] Theor. Comput. Sci., 1989, v:68, n:3, pp:267-276 [Journal] - Neil Immerman, Sushant Patnaik, David W. Stemple
**The Expressiveness of a Family of Finite Set Languages.**[Citation Graph (0, 0)][DBLP] Theor. Comput. Sci., 1996, v:155, n:1, pp:111-140 [Journal] - Micah Adler, Neil Immerman
**An**[Citation Graph (0, 0)][DBLP]*n!*lower bound on formula size. ACM Trans. Comput. Log., 2003, v:4, n:3, pp:296-314 [Journal] - P. Weis, Neil Immerman
**Structure Theorem and Strict Alternation Hierarchy for FO**[Citation Graph (0, 0)][DBLP]^{2}on Words. CSL, 2007, pp:343-357 [Conf] - Rajeev Alur, Marcelo Arenas, Pablo Barceló, Kousha Etessami, Neil Immerman, Leonid Libkin
**First-Order and Temporal Logics for Nested Words.**[Citation Graph (0, 0)][DBLP] LICS, 2007, pp:151-160 [Conf] **Learning Generalized Plans Using Abstract Counting.**[Citation Graph (, )][DBLP]**Computing Applicability Conditions for Plans with Loops.**[Citation Graph (, )][DBLP]**Merging example plans into generalized plans for non-deterministic environments.**[Citation Graph (, )][DBLP]**Finding Reductions Automatically.**[Citation Graph (, )][DBLP]**Structure Theorem and Strict Alternation Hierarchy for FO**[Citation Graph (, )][DBLP]^{2}on Words.**On Supporting Kleene Closure over Event Streams.**[Citation Graph (, )][DBLP]**Abstract Planning with Unknown Object Quantities and Properties.**[Citation Graph (, )][DBLP]**Efficient pattern matching over event streams.**[Citation Graph (, )][DBLP]**Constructing Specialized Shape Analyses for Uniform Change.**[Citation Graph (, )][DBLP]**First-Order and Temporal Logics for Nested Words**[Citation Graph (, )][DBLP]**Simulating reachability using first-order logic with applications to verification of linked data structures**[Citation Graph (, )][DBLP]**Structure Theorem and Strict Alternation Hierarchy for FO^2 on Words**[Citation Graph (, )][DBLP]**Structure Theorem and Strict Alternation Hierarchy for FO^2 on Words.**[Citation Graph (, )][DBLP]
Search in 0.006secs, Finished in 0.011secs | |||||||

| |||||||

| |||||||

System created by asidirop@csd.auth.gr [http://users.auth.gr/~asidirop/] © 2002 for Data Engineering Laboratory, Department of Informatics, Aristotle University © 2002 |