×
Author ID: immerman.neil Recent zbMATH articles by "Immerman, Neil"
Published as: Immerman, Neil; Immerman, N.; Immerman, Niel
External Links: MGP · Wikidata · dblp · GND · IdRef

Publications by Year

Citations contained in zbMATH Open

53 Publications have been cited 1,636 times in 1,166 Documents Cited by Year
Nondeterministic space is closed under complementation. Zbl 0668.68056
Immerman, Neil
222
1988
Descriptive complexity. Zbl 0918.68031
Immerman, Neil
178
1999
Languages that capture complexity classes. Zbl 0634.68034
Immerman, Neil
156
1987
Relational queries computable in polynomial time. Zbl 0612.68086
Immerman, Neil
145
1986
On uniformity within \(NC^ 1\). Zbl 0719.68023
Barrington, David A. Mix; Immerman, Neil; Straubing, Howard
144
1990
An optimal lower bound on the number of variables for graph identification. Zbl 0785.68043
Cai, Jin-Yi; Fürer, Martin; Immerman, Neil
133
1992
Upper and lower bounds for first order expressibility. Zbl 0503.68032
Immerman, Neil
67
1982
Number of quantifiers is better than number of tape cells. Zbl 0486.03019
Immerman, Neil
61
1981
Expressibility and parallel complexity. Zbl 0688.68038
Immerman, Neil
47
1989
Sparse sets in NP-P: EXPTIME versus NEXPTIME. Zbl 0586.68042
Hartmanis, J.; Immerman, N.; Sewelson, V.
47
1985
The complexity of decentralized control of Markov decision processes. Zbl 1082.90593
Bernstein, Daniel S.; Givan, Robert; Immerman, Neil; Zilberstein, Shlomo
44
2002
Definability with bounded number of bound variables. Zbl 0711.03004
Immerman, Neil; Kozen, Dexter
35
1989
First-order and temporal logics for nested words. Zbl 1159.03018
Alur, Rajeev; Arenas, Marcelo; Barcelo, Pablo; Etessami, Kousha; Immerman, Neil; Libkin, Leonid
30
2008
Descriptive complexity and model checking. Zbl 0945.03546
Immerman, Neil
24
1998
Descriptive and computational complexity. Zbl 0675.68032
Immerman, Neil
23
1989
Dyn-FO: A parallel, dynamic complexity class. Zbl 0889.68063
Patnaik, Sushant; Immerman, Neil
22
1997
The complexity of iterated multiplication. Zbl 0818.68076
Immerman, Neil; Landau, Susan
20
1995
Descriptive complexity: a logician’s approach to computation. Zbl 1042.68604
Immerman, N.
17
1995
The boundary between decidability and undecidability for transitive-closure logics. Zbl 1095.03008
Immerman, Neil; Rabinovich, Alex; Reps, Tom; Sagiv, Mooly; Yorsh, Greta
16
2004
The complexity of satisfiability problems: Refining Schaefer’s theorem. Zbl 1161.68487
Allender, Eric; Bauland, Michael; Immerman, Neil; Schnoor, Henning; Vollmer, Heribert
16
2009
Structure theorem and strict alternation hierarchy for FO\(^{2}\) on words. Zbl 1168.03019
Weis, Philipp; Immerman, Neil
15
2009
The complexity of satisfiability problems: Refining Schaefer’s theorem. Zbl 1156.68396
Allender, Eric; Bauland, Michael; Immerman, Neil; Schnoor, Henning; Vollmer, Heribert
13
2005
Simulating reachability using first-order logic with applications to verification of linked data structures. Zbl 1135.68556
Lev-Ami, T.; Immerman, N.; Reps, T.; Sagiv, M.; Srivastava, S.; Yorsh, G.
13
2005
Progress in descriptive complexity. Zbl 0959.68523
Immerman, Neil
11
1999
A new representation and associated algorithms for generalized planning. Zbl 1216.68253
Srivastava, Siddharth; Immerman, Neil; Zilberstein, Shlomo
10
2011
An \(n!\) lower bound on formula size. Zbl 1365.68270
Adler, Micah; Immerman, Neil
10
2003
On complete problems for \(NP\cap C_ 0NP\). Zbl 0576.68032
Hartmanis, Juris; Immerman, Neil
8
1985
On the unusual effectiveness of logic in computer science. Zbl 0979.03033
Halpern, Joseph Y.; Harper, Robert; Immerman, Neil; Kolaitis, Phokion G.; Vardi, Moshe Y.; Vianu, Victor
7
2001
A first-order isomorphism theorem. Zbl 0874.68124
Allender, Eric; Balcázar, José; Immerman, Neil
7
1997
The expressiveness of a family of finite set languages. Zbl 0874.68093
Immerman, Neil; Patnaik, Sushant; Stemple, David
7
1996
A first-order isomorphism theorem. Zbl 0799.68088
Allender, Eric; Balcázar, Jose; Immerman, Neil
7
1993
Experimental descriptive complexity. Zbl 1354.68103
Carmosino, Marco; Immerman, Neil; Jordan, Charles
7
2012
Applicability conditions for plans with loops: computability results and algorithms. Zbl 1270.68277
Srivastava, Siddharth; Immerman, Neil; Zilberstein, Shlomo
6
2012
Time, hardware, and uniformity. Zbl 0880.68037
Barrington, David Mix; Immerman, Neil
6
1997
Decentralizing SDN policies. Zbl 1346.68027
Padon, Oded; Immerman, Neil; Karbyshev, Aleksandr; Lahav, Ori; Sagiv, Mooly; Shoham, Sharon
6
2015
Reachability logic: An efficient fragment of transitive closure logic. Zbl 0948.03022
Alechina, Natasha; Immerman, Neil
5
2000
First-order expressibility of languages with neutral letters or: The Crane Beach conjecture. Zbl 1069.03021
Barrington, David A. Mix; Immerman, Neil; Lautemann, Clemens; Schweikardt, Nicole; Thérien, Denis
5
2005
Verification via structure simulation. Zbl 1103.68623
Immerman, Niel; Rabinovich, Alexander; Reps, Thomas W.; Sagiv, Mooly; Yorsh, Great
5
2004
Relativizing relativized computations. Zbl 0679.68084
Immerman, Neil; Mahaney, Stephen R.
5
1989
Modular reasoning about heap paths via effectively propositional formulas. Zbl 1284.68403
Itzhaky, Shachar; Banerjee, Anindya; Immerman, Neil; Lahav, Ori; Nanevski, Aleksandar; Sagiv, Mooly
5
2014
Decidability of inferring inductive invariants. Zbl 1347.68234
Padon, Oded; Immerman, Neil; Shoham, Sharon; Karbyshev, Aleksandr; Sagiv, Mooly
5
2016
Reachability and the power of local ordering. Zbl 0941.68584
Etessami, Kousha; Immerman, Neil
3
1994
Tree canonization and transitive closure. Zbl 1005.03515
Etessami, Kousha; Immerman, Neil
3
2000
Reachability and the power of local ordering. Zbl 0884.68053
Etessami, Kousha; Immerman, Neil
3
1995
Descriptive and computational complexity. Zbl 0756.68041
Immerman, Neil
3
1989
Bounded quantifier instantiation for checking inductive invariants. Zbl 1509.68162
Feldman, Yotam M. Y.; Padon, Oded; Immerman, Neil; Sagiv, Mooly; Shoham, Sharon
3
2019
Interpreting logics of knowledge in propositional dynamic logic. Zbl 0634.03012
Fischer, Michael J.; Immerman, Neil
3
1987
Number of variables is equivalent to space. Zbl 0986.68040
Immerman, Neil; Buss, Jonathan F.; Barrington, David A. Mix
2
2001
Structure theorem and strict alternation hierarchy for FO\(^{2}\) on words. Zbl 1168.03328
Weis, P.; Immerman, N.
2
2007
Simulating reachability using first-order logic with applications to verification of linked data structures. Zbl 1163.68010
Lev-Ami, Tal; Immerman, Neil; Reps, Thomas W.; Sagiv, Mooly; Srivastava, Siddharth; Yorsh, Greta
1
2009
Finding reductions automatically. Zbl 1287.68024
Crouch, Michael; Immerman, Neil; Moss, J. Eliot B.
1
2010
Solving geometry problems using a combination of symbolic and numerical reasoning. Zbl 1407.68513
Itzhaky, Shachar; Gulwani, Sumit; Immerman, Neil; Sagiv, Mooly
1
2013
Bounded quantifier instantiation for checking inductive invariants. Zbl 1452.68119
Feldman, Yotam M. Y.; Padon, Oded; Immerman, Neil; Sagiv, Mooly; Shoham, Sharon
1
2017
Bounded quantifier instantiation for checking inductive invariants. Zbl 1509.68162
Feldman, Yotam M. Y.; Padon, Oded; Immerman, Neil; Sagiv, Mooly; Shoham, Sharon
3
2019
Bounded quantifier instantiation for checking inductive invariants. Zbl 1452.68119
Feldman, Yotam M. Y.; Padon, Oded; Immerman, Neil; Sagiv, Mooly; Shoham, Sharon
1
2017
Decidability of inferring inductive invariants. Zbl 1347.68234
Padon, Oded; Immerman, Neil; Shoham, Sharon; Karbyshev, Aleksandr; Sagiv, Mooly
5
2016
Decentralizing SDN policies. Zbl 1346.68027
Padon, Oded; Immerman, Neil; Karbyshev, Aleksandr; Lahav, Ori; Sagiv, Mooly; Shoham, Sharon
6
2015
Modular reasoning about heap paths via effectively propositional formulas. Zbl 1284.68403
Itzhaky, Shachar; Banerjee, Anindya; Immerman, Neil; Lahav, Ori; Nanevski, Aleksandar; Sagiv, Mooly
5
2014
Solving geometry problems using a combination of symbolic and numerical reasoning. Zbl 1407.68513
Itzhaky, Shachar; Gulwani, Sumit; Immerman, Neil; Sagiv, Mooly
1
2013
Experimental descriptive complexity. Zbl 1354.68103
Carmosino, Marco; Immerman, Neil; Jordan, Charles
7
2012
Applicability conditions for plans with loops: computability results and algorithms. Zbl 1270.68277
Srivastava, Siddharth; Immerman, Neil; Zilberstein, Shlomo
6
2012
A new representation and associated algorithms for generalized planning. Zbl 1216.68253
Srivastava, Siddharth; Immerman, Neil; Zilberstein, Shlomo
10
2011
Finding reductions automatically. Zbl 1287.68024
Crouch, Michael; Immerman, Neil; Moss, J. Eliot B.
1
2010
The complexity of satisfiability problems: Refining Schaefer’s theorem. Zbl 1161.68487
Allender, Eric; Bauland, Michael; Immerman, Neil; Schnoor, Henning; Vollmer, Heribert
16
2009
Structure theorem and strict alternation hierarchy for FO\(^{2}\) on words. Zbl 1168.03019
Weis, Philipp; Immerman, Neil
15
2009
Simulating reachability using first-order logic with applications to verification of linked data structures. Zbl 1163.68010
Lev-Ami, Tal; Immerman, Neil; Reps, Thomas W.; Sagiv, Mooly; Srivastava, Siddharth; Yorsh, Greta
1
2009
First-order and temporal logics for nested words. Zbl 1159.03018
Alur, Rajeev; Arenas, Marcelo; Barcelo, Pablo; Etessami, Kousha; Immerman, Neil; Libkin, Leonid
30
2008
Structure theorem and strict alternation hierarchy for FO\(^{2}\) on words. Zbl 1168.03328
Weis, P.; Immerman, N.
2
2007
The complexity of satisfiability problems: Refining Schaefer’s theorem. Zbl 1156.68396
Allender, Eric; Bauland, Michael; Immerman, Neil; Schnoor, Henning; Vollmer, Heribert
13
2005
Simulating reachability using first-order logic with applications to verification of linked data structures. Zbl 1135.68556
Lev-Ami, T.; Immerman, N.; Reps, T.; Sagiv, M.; Srivastava, S.; Yorsh, G.
13
2005
First-order expressibility of languages with neutral letters or: The Crane Beach conjecture. Zbl 1069.03021
Barrington, David A. Mix; Immerman, Neil; Lautemann, Clemens; Schweikardt, Nicole; Thérien, Denis
5
2005
The boundary between decidability and undecidability for transitive-closure logics. Zbl 1095.03008
Immerman, Neil; Rabinovich, Alex; Reps, Tom; Sagiv, Mooly; Yorsh, Greta
16
2004
Verification via structure simulation. Zbl 1103.68623
Immerman, Niel; Rabinovich, Alexander; Reps, Thomas W.; Sagiv, Mooly; Yorsh, Great
5
2004
An \(n!\) lower bound on formula size. Zbl 1365.68270
Adler, Micah; Immerman, Neil
10
2003
The complexity of decentralized control of Markov decision processes. Zbl 1082.90593
Bernstein, Daniel S.; Givan, Robert; Immerman, Neil; Zilberstein, Shlomo
44
2002
On the unusual effectiveness of logic in computer science. Zbl 0979.03033
Halpern, Joseph Y.; Harper, Robert; Immerman, Neil; Kolaitis, Phokion G.; Vardi, Moshe Y.; Vianu, Victor
7
2001
Number of variables is equivalent to space. Zbl 0986.68040
Immerman, Neil; Buss, Jonathan F.; Barrington, David A. Mix
2
2001
Reachability logic: An efficient fragment of transitive closure logic. Zbl 0948.03022
Alechina, Natasha; Immerman, Neil
5
2000
Tree canonization and transitive closure. Zbl 1005.03515
Etessami, Kousha; Immerman, Neil
3
2000
Descriptive complexity. Zbl 0918.68031
Immerman, Neil
178
1999
Progress in descriptive complexity. Zbl 0959.68523
Immerman, Neil
11
1999
Descriptive complexity and model checking. Zbl 0945.03546
Immerman, Neil
24
1998
Dyn-FO: A parallel, dynamic complexity class. Zbl 0889.68063
Patnaik, Sushant; Immerman, Neil
22
1997
A first-order isomorphism theorem. Zbl 0874.68124
Allender, Eric; Balcázar, José; Immerman, Neil
7
1997
Time, hardware, and uniformity. Zbl 0880.68037
Barrington, David Mix; Immerman, Neil
6
1997
The expressiveness of a family of finite set languages. Zbl 0874.68093
Immerman, Neil; Patnaik, Sushant; Stemple, David
7
1996
The complexity of iterated multiplication. Zbl 0818.68076
Immerman, Neil; Landau, Susan
20
1995
Descriptive complexity: a logician’s approach to computation. Zbl 1042.68604
Immerman, N.
17
1995
Reachability and the power of local ordering. Zbl 0884.68053
Etessami, Kousha; Immerman, Neil
3
1995
Reachability and the power of local ordering. Zbl 0941.68584
Etessami, Kousha; Immerman, Neil
3
1994
A first-order isomorphism theorem. Zbl 0799.68088
Allender, Eric; Balcázar, Jose; Immerman, Neil
7
1993
An optimal lower bound on the number of variables for graph identification. Zbl 0785.68043
Cai, Jin-Yi; Fürer, Martin; Immerman, Neil
133
1992
On uniformity within \(NC^ 1\). Zbl 0719.68023
Barrington, David A. Mix; Immerman, Neil; Straubing, Howard
144
1990
Expressibility and parallel complexity. Zbl 0688.68038
Immerman, Neil
47
1989
Definability with bounded number of bound variables. Zbl 0711.03004
Immerman, Neil; Kozen, Dexter
35
1989
Descriptive and computational complexity. Zbl 0675.68032
Immerman, Neil
23
1989
Relativizing relativized computations. Zbl 0679.68084
Immerman, Neil; Mahaney, Stephen R.
5
1989
Descriptive and computational complexity. Zbl 0756.68041
Immerman, Neil
3
1989
Nondeterministic space is closed under complementation. Zbl 0668.68056
Immerman, Neil
222
1988
Languages that capture complexity classes. Zbl 0634.68034
Immerman, Neil
156
1987
Interpreting logics of knowledge in propositional dynamic logic. Zbl 0634.03012
Fischer, Michael J.; Immerman, Neil
3
1987
Relational queries computable in polynomial time. Zbl 0612.68086
Immerman, Neil
145
1986
Sparse sets in NP-P: EXPTIME versus NEXPTIME. Zbl 0586.68042
Hartmanis, J.; Immerman, N.; Sewelson, V.
47
1985
On complete problems for \(NP\cap C_ 0NP\). Zbl 0576.68032
Hartmanis, Juris; Immerman, Neil
8
1985
Upper and lower bounds for first order expressibility. Zbl 0503.68032
Immerman, Neil
67
1982
Number of quantifiers is better than number of tape cells. Zbl 0486.03019
Immerman, Neil
61
1981
all top 5

Cited by 1,457 Authors

24 Grohe, Martin
23 Allender, Eric W.
23 Vollmer, Heribert
18 Verbitsky, Oleg
17 Hella, Lauri T.
17 Immerman, Neil
17 Stewart, Iain A.
16 Dawar, Anuj
16 Geffert, Viliam
16 Hemaspaandra, Lane A.
14 Chatterjee, Krishnendu
14 Grädel, Erich
14 Köbler, Johannes
13 Holzer, Markus
13 Kolaitis, Phokion G.
12 Krebs, Andreas
12 Kufleitner, Manfred
12 McKenzie, Pierre
12 Tantau, Till
11 Schwentick, Thomas
10 Mix Barrington, David A.
10 Pradella, Matteo
10 Vardi, Moshe Ya’akov
10 Vianu, Victor
9 Flum, Jörg
9 Libkin, Leonid O.
9 Makowsky, Johann-Andreas
9 Mandrioli, Dino
9 Ponomarenko, Ilya Nikolaevich
9 Thérien, Denis
8 Arvind, Vikraman
8 Chen, Yijia
8 Datta, Samir
8 Fuhlbrück, Frank
8 Henzinger, Thomas A.
8 Kontinen, Juha
8 Kupferman, Orna
8 Schweikardt, Nicole
8 Straubing, Howard
8 Turull Torres, Jose Maria
8 Zeume, Thomas
7 Kuusisto, Antti
7 Neuen, Daniel
7 Ogihara, Mitsunori
7 Sagiv, Mooly
7 Van den Bussche, Jan
6 Abiteboul, Serge
6 Atserias, Albert
6 Cai, Jin-Yi
6 Durand, Arnaud
6 Fleischer, Lukas
6 Grandjean, Etienne
6 Jenner, Birgit
6 Jeřábek, Emil
6 Kiefer, Sandra
6 Lange, Klaus-Jörn
6 Otto, Martin
6 Pakusa, Wied
6 Rauch Henzinger, Monika
6 Schweitzer, Pascal
5 Agrawal, Manindra
5 Àlvarez, Carme
5 Benedikt, Michael A.
5 Berkholz, Christoph
5 Bollig, Benedikt
5 Chen, Hubie
5 Chiari, Michele
5 Cook, Stephen Arthur
5 Eiter, Thomas
5 Elberfeld, Michael
5 Fagin, Ronald
5 Ferrarotti, Flavio Antonio
5 Gottlob, Georg
5 Gurevich, Yuri
5 Haak, Anselm
5 Huynh, Dung T.
5 Ibarra, Oscar H.
5 Jakobi, Sebastian
5 Lange, Martin
5 Lautemann, Clemens
5 Luosto, Kerkko
5 Masopust, Tomáš
5 Rabinovich, Alexander
5 Schnoor, Henning
5 Suciu, Dan Mircea
5 Szepietowski, Andrzej
5 Torán, Jacobo
5 Vortmeier, Nils
5 Zhukovskiĭ, Maksim Evgen’evich
4 Aspnes, James
4 Balcázar, José Luis
4 Bannach, Max
4 Beigel, Richard
4 Bodirsky, Manuel
4 Buhrman, Harry
4 Clote, Peter G.
4 Compton, Kevin J.
4 Creignou, Nadia
4 Damm, Carsten
4 de Rijke, Maarten
...and 1,357 more Authors
all top 5

Cited in 117 Serials

154 Theoretical Computer Science
82 Journal of Computer and System Sciences
82 Information and Computation
39 Information Processing Letters
35 Theory of Computing Systems
33 Artificial Intelligence
29 Annals of Pure and Applied Logic
26 The Journal of Symbolic Logic
26 Logical Methods in Computer Science
18 International Journal of Foundations of Computer Science
17 Computational Complexity
15 Acta Informatica
14 Annals of Mathematics and Artificial Intelligence
13 ACM Transactions on Computational Logic
12 Mathematical Systems Theory
11 RAIRO. Informatique Théorique et Applications
9 SIAM Journal on Computing
9 Mathematical Logic Quarterly (MLQ)
9 The Journal of Artificial Intelligence Research (JAIR)
9 The Bulletin of Symbolic Logic
7 Studia Logica
7 Journal of Automated Reasoning
6 Discrete Applied Mathematics
6 Algorithmica
6 Archive for Mathematical Logic
5 European Journal of Combinatorics
5 Journal of Symbolic Computation
5 International Journal of Algebra and Computation
5 Mathematical Structures in Computer Science
5 Formal Methods in System Design
5 Journal of Applied Non-Classical Logics
5 RAIRO. Theoretical Informatics and Applications
4 Discrete Mathematics
4 SIAM Journal on Discrete Mathematics
4 Journal of the ACM
4 Journal of Machine Learning Research (JMLR)
4 Journal of Applied Logic
3 Algebra Universalis
3 Information Sciences
3 Journal of Combinatorial Theory. Series B
3 Graphs and Combinatorics
3 Journal of Complexity
3 Formal Aspects of Computing
3 Annals of Operations Research
3 Distributed Computing
3 Computer Science Review
2 Automatica
2 Journal of Combinatorial Theory. Series A
2 Journal of Graph Theory
2 Journal of Philosophical Logic
2 Operations Research
2 Semigroup Forum
2 Combinatorica
2 European Journal of Operational Research
2 Journal of Algebraic Combinatorics
2 Journal of Logic, Language and Information
2 Journal of Mathematical Sciences (New York)
2 Constraints
2 Journal of Combinatorial Optimization
2 Journal of Graph Algorithms and Applications
2 Mathematical and Computer Modelling of Dynamical Systems
2 Theory and Practice of Logic Programming
2 International Journal of Parallel, Emergent and Distributed Systems
2 The Review of Symbolic Logic
2 Dynamic Games and Applications
2 ACM Transactions on Computation Theory
1 Computers & Mathematics with Applications
1 Journal of Statistical Physics
1 Problems of Information Transmission
1 Archivum Mathematicum
1 International Journal of Game Theory
1 Journal of Mathematical Psychology
1 Journal of Pure and Applied Algebra
1 Naval Research Logistics
1 Synthese
1 Moscow University Computational Mathematics and Cybernetics
1 Advances in Applied Mathematics
1 Ergodic Theory and Dynamical Systems
1 Mathematical Social Sciences
1 Journal of Computer Science and Technology
1 New Generation Computing
1 International Journal of Approximate Reasoning
1 Neural Networks
1 JETAI. Journal of Experimental & Theoretical Artificial Intelligence
1 Neural Computation
1 Discrete Event Dynamic Systems
1 Linear Algebra and its Applications
1 International Journal of Robust and Nonlinear Control
1 The Australasian Journal of Combinatorics
1 St. Petersburg Mathematical Journal
1 Advances in Applied Clifford Algebras
1 The Electronic Journal of Combinatorics
1 Acta Mathematica et Informatica Universitatis Ostraviensis
1 Doklady Mathematics
1 Soft Computing
1 LMS Journal of Computation and Mathematics
1 Lobachevskii Journal of Mathematics
1 International Journal of Modern Physics C
1 International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems
1 The Journal of Logic and Algebraic Programming
...and 17 more Serials

Citations by Year

The data are displayed as stored in Wikidata under a Creative Commons CC0 License. Updates and corrections should be made in Wikidata.