The SCEAS System
Navigation Menu

Search the dblp DataBase

Title:
Author:

Neil Immerman: [Publications] [Author Rank by year] [Co-authors] [Prefers] [Cites] [Cited by]

Publications of Author

  1. 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]
  2. Neil Immerman
    Languages that Capture Complexity Classes. [Citation Graph (26, 0)][DBLP]
    SIAM J. Comput., 1987, v:16, n:4, pp:760-778 [Journal]
  3. 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]
  4. Neil Immerman
    Relational Queries Computable in Polynomial Time (Extended Abstract) [Citation Graph (14, 0)][DBLP]
    STOC, 1982, pp:147-152 [Conf]
  5. 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]
  6. Sushant Patnaik, Neil Immerman
    Dyn-FO: A Parallel, Dynamic Complexity Class. [Citation Graph (9, 20)][DBLP]
    PODS, 1994, pp:210-221 [Conf]
  7. 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]
  8. 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]
  9. Neil Immerman
    Expressibility and Parallel Complexity. [Citation Graph (6, 0)][DBLP]
    SIAM J. Comput., 1989, v:18, n:3, pp:625-638 [Journal]
  10. 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]
  11. 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]
  12. 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]
  13. Kousha Etessami, Neil Immerman
    Tree Canonization and Transitive Closure [Citation Graph (3, 0)][DBLP]
    LICS, 1995, pp:331-341 [Conf]
  14. Neil Immerman
    Languages Which Capture Complexity Classes (Preliminary Report) [Citation Graph (3, 0)][DBLP]
    STOC, 1983, pp:347-354 [Conf]
  15. 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]
  16. 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]
  17. Neil Immerman, Moshe Y. Vardi
    Model Checking and Transitive-Closure Logic. [Citation Graph (1, 0)][DBLP]
    CAV, 1997, pp:291-302 [Conf]
  18. Neil Immerman
    Length of Predicate Calculus Formulas as a New Complexity Measure [Citation Graph (1, 0)][DBLP]
    FOCS, 1979, pp:337-347 [Conf]
  19. 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]
  20. 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]
  21. 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]
  22. 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]
  23. 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]
  24. Neil Immerman
    DSPACE[nk] = VAR[k+1]. [Citation Graph (0, 0)][DBLP]
    Structure in Complexity Theory Conference, 1991, pp:334-340 [Conf]
  25. Neil Immerman, Susan Landau
    The Complexity of Iterated Multiplication. [Citation Graph (0, 0)][DBLP]
    Structure in Complexity Theory Conference, 1989, pp:104-111 [Conf]
  26. 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]
  27. 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]
  28. Neil Immerman
    Descriptive and Computational Complexity. [Citation Graph (0, 0)][DBLP]
    FCT, 1989, pp:244-245 [Conf]
  29. Juris Hartmanis, Neil Immerman, Stephen R. Mahaney
    One-Way Log-Tape Reductions [Citation Graph (0, 0)][DBLP]
    FOCS, 1978, pp:65-72 [Conf]
  30. Neil Immerman
    Upper and Lower Bounds for First Order Expressibility [Citation Graph (0, 0)][DBLP]
    FOCS, 1980, pp:74-82 [Conf]
  31. Neil Immerman
    Descriptive Complexity and Model Checking. [Citation Graph (0, 0)][DBLP]
    FSTTCS, 1998, pp:1-5 [Conf]
  32. Juris Hartmanis, Neil Immerman
    On Complete Problems for NP$\cap$CoNP. [Citation Graph (0, 0)][DBLP]
    ICALP, 1985, pp:250-259 [Conf]
  33. 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]
  34. 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]
  35. Micah Adler, Neil Immerman
    An n! Lower Bound on Formula Size. [Citation Graph (0, 0)][DBLP]
    LICS, 2001, pp:197-0 [Conf]
  36. Yuri Gurevich, Neil Immerman, Saharon Shelah
    McColm's Conjecture [Citation Graph (0, 0)][DBLP]
    LICS, 1994, pp:10-19 [Conf]
  37. William Hesse, Neil Immerman
    Complete Problems for Dynamic Complexity Classes. [Citation Graph (0, 0)][DBLP]
    LICS, 2002, pp:313-0 [Conf]
  38. Neil Immerman, Dexter Kozen
    Definability with Bounded Number of Bound Variables [Citation Graph (0, 0)][DBLP]
    LICS, 1987, pp:236-244 [Conf]
  39. J. Antonio Medina, Neil Immerman
    A Syntactic Characterization of NP-Completeness [Citation Graph (0, 0)][DBLP]
    LICS, 1994, pp:241-250 [Conf]
  40. J. Antonio Medina, Neil Immerman
    A Generalization of Fagin's Theorem. [Citation Graph (0, 0)][DBLP]
    LICS, 1996, pp:2-12 [Conf]
  41. 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]
  42. Eric Allender, José L. Balcázar, Neil Immerman
    A First-Order Isomorphism Theorem. [Citation Graph (0, 0)][DBLP]
    STACS, 1993, pp:163-174 [Conf]
  43. Kousha Etessami, Neil Immerman
    Reachability and the Power of Local Ordering. [Citation Graph (0, 0)][DBLP]
    STACS, 1994, pp:123-135 [Conf]
  44. 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]
  45. Michael J. Fischer, Neil Immerman
    Foundations of Knowledge for Distributed Systems. [Citation Graph (0, 0)][DBLP]
    TARK, 1986, pp:171-185 [Conf]
  46. 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]
  47. 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]
  48. 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]
  49. 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]
  50. Neil Immerman
    Progress in Descriptive Complexity. [Citation Graph (0, 0)][DBLP]
    Bulletin of the EATCS, 1999, v:67, n:, pp:72-81 [Journal]
  51. 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]
  52. 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]
  53. 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]
  54. 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]
  55. 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]
  56. 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]
  57. 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]
  58. 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]
  59. 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]
  60. 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]
  61. 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]
  62. Micah Adler, Neil Immerman
    An n! lower bound on formula size. [Citation Graph (0, 0)][DBLP]
    ACM Trans. Comput. Log., 2003, v:4, n:3, pp:296-314 [Journal]
  63. P. Weis, Neil Immerman
    Structure Theorem and Strict Alternation Hierarchy for FO2 on Words. [Citation Graph (0, 0)][DBLP]
    CSL, 2007, pp:343-357 [Conf]
  64. 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]

  65. Learning Generalized Plans Using Abstract Counting. [Citation Graph (, )][DBLP]


  66. Computing Applicability Conditions for Plans with Loops. [Citation Graph (, )][DBLP]


  67. Merging example plans into generalized plans for non-deterministic environments. [Citation Graph (, )][DBLP]


  68. Finding Reductions Automatically. [Citation Graph (, )][DBLP]


  69. Structure Theorem and Strict Alternation Hierarchy for FO2 on Words. [Citation Graph (, )][DBLP]


  70. On Supporting Kleene Closure over Event Streams. [Citation Graph (, )][DBLP]


  71. Abstract Planning with Unknown Object Quantities and Properties. [Citation Graph (, )][DBLP]


  72. Efficient pattern matching over event streams. [Citation Graph (, )][DBLP]


  73. Constructing Specialized Shape Analyses for Uniform Change. [Citation Graph (, )][DBLP]


  74. First-Order and Temporal Logics for Nested Words [Citation Graph (, )][DBLP]


  75. Simulating reachability using first-order logic with applications to verification of linked data structures [Citation Graph (, )][DBLP]


  76. Structure Theorem and Strict Alternation Hierarchy for FO^2 on Words [Citation Graph (, )][DBLP]


  77. Structure Theorem and Strict Alternation Hierarchy for FO^2 on Words. [Citation Graph (, )][DBLP]


Search in 0.555secs, Finished in 0.557secs
NOTICE1
System may not be available sometimes or not working properly, since it is still in development with continuous upgrades
NOTICE2
The rankings that are presented on this page should NOT be considered as formal since the citation info is incomplete in DBLP
 
System created by asidirop@csd.auth.gr [http://users.auth.gr/~asidirop/] © 2002
for Data Engineering Laboratory, Department of Informatics, Aristotle University © 2002