×

zbMATH — the first resource for mathematics

Immerman, Neil

Compute Distance To:
Author ID: immerman.neil Recent zbMATH articles by "Immerman, Neil"
Published as: Immerman, N.; Immerman, Neil; Immerman, Niel
External Links: MGP · Wikidata · dblp · GND
Documents Indexed: 58 Publications since 1981, including 3 Books

Publications by Year

Citations contained in zbMATH Open

49 Publications have been cited 1,221 times in 846 Documents Cited by Year
Nondeterministic space is closed under complementation. Zbl 0668.68056
Immerman, Neil
186
1988
Languages that capture complexity classes. Zbl 0634.68034
Immerman, Neil
133
1987
Relational queries computable in polynomial time. Zbl 0612.68086
Immerman, Neil
124
1986
On uniformity within \(NC^ 1\). Zbl 0719.68023
Barrington, David A. Mix; Immerman, Neil; Straubing, Howard
104
1990
Descriptive complexity. Zbl 0918.68031
Immerman, Neil
101
1999
An optimal lower bound on the number of variables for graph identification. Zbl 0785.68043
Cai, Jin-Yi; Fürer, Martin; Immerman, Neil
72
1992
Upper and lower bounds for first order expressibility. Zbl 0503.68032
Immerman, Neil
52
1982
Number of quantifiers is better than number of tape cells. Zbl 0486.03019
Immerman, Neil
45
1981
Sparse sets in NP-P: EXPTIME versus NEXPTIME. Zbl 0586.68042
Hartmanis, J.; Immerman, N.; Sewelson, V.
43
1985
Descriptive complexity and model checking. Zbl 0945.03546
Immerman, Neil
34
1998
Expressibility and parallel complexity. Zbl 0688.68038
Immerman, Neil
33
1989
Definability with bounded number of bound variables. Zbl 0711.03004
Immerman, Neil; Kozen, Dexter
31
1989
The complexity of decentralized control of Markov decision processes. Zbl 1082.90593
Bernstein, Daniel S.; Givan, Robert; Immerman, Neil; Zilberstein, Shlomo
24
2002
First-order and temporal logics for nested words. Zbl 1159.03018
Alur, Rajeev; Arenas, Marcelo; Barcelo, Pablo; Etessami, Kousha; Immerman, Neil; Libkin, Leonid
21
2008
Progress in descriptive complexity. Zbl 0959.68523
Immerman, Neil
20
1999
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.
15
1995
Descriptive and computational complexity. Zbl 0756.68041
Immerman, Neil
14
1989
The complexity of satisfiability problems: Refining Schaefer’s theorem. Zbl 1161.68487
Allender, Eric; Bauland, Michael; Immerman, Neil; Schnoor, Henning; Vollmer, Heribert
11
2009
The complexity of satisfiability problems: Refining Schaefer’s theorem. Zbl 1156.68396
Allender, Eric; Bauland, Michael; Immerman, Neil; Schnoor, Henning; Vollmer, Heribert
11
2005
The boundary between decidability and undecidability for transitive-closure logics. Zbl 1095.03008
Immerman, Neil; Rabinovich, Alex; Reps, Tom; Sagiv, Mooly; Yorsh, Greta
11
2004
An \(n!\) lower bound on formula size. Zbl 1365.68270
Adler, Micah; Immerman, Neil
9
2003
Dyn-FO: A parallel, dynamic complexity class. Zbl 0889.68063
Patnaik, Sushant; Immerman, Neil
9
1997
Structure theorem and strict alternation hierarchy for FO\(^{2}\) on words. Zbl 1168.03019
Weis, Philipp; Immerman, Neil
7
2009
The expressiveness of a family of finite set languages. Zbl 0874.68093
Immerman, Neil; Patnaik, Sushant; Stemple, David
7
1996
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
6
2001
Time, hardware, and uniformity. Zbl 0880.68037
Barrington, David Mix; Immerman, Neil
6
1997
A first-order isomorphism theorem. Zbl 0799.68088
Allender, Eric; Balcázar, Jose; Immerman, Neil
6
1993
On complete problems for \(NP\cap C_ 0NP\). Zbl 0576.68032
Hartmanis, Juris; Immerman, Neil
6
1985
A new representation and associated algorithms for generalized planning. Zbl 1216.68253
Srivastava, Siddharth; Immerman, Neil; Zilberstein, Shlomo
5
2011
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.
5
2005
Reachability logic: An efficient fragment of transitive closure logic. Zbl 0948.03022
Alechina, Natasha; Immerman, Neil
5
2000
Relativizing relativized computations. Zbl 0679.68084
Immerman, Neil; Mahaney, Stephen R.
5
1989
Verification via structure simulation. Zbl 1103.68623
Immerman, Niel; Rabinovich, Alexander; Reps, Thomas W.; Sagiv, Mooly; Yorsh, Great
4
2004
A first-order isomorphism theorem. Zbl 0874.68124
Allender, Eric; Balcázar, José; Immerman, Neil
4
1997
Modular reasoning about heap paths via effectively propositional formulas. Zbl 1284.68403
Itzhaky, Shachar; Banerjee, Anindya; Immerman, Neil; Lahav, Ori; Nanevski, Aleksandar; Sagiv, Mooly
3
2014
Applicability conditions for plans with loops: computability results and algorithms. Zbl 1270.68277
Srivastava, Siddharth; Immerman, Neil; Zilberstein, Shlomo
3
2012
Experimental descriptive complexity. Zbl 1354.68103
Carmosino, Marco; Immerman, Neil; Jordan, Charles
3
2012
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
Reachability and the power of local ordering. Zbl 0941.68584
Etessami, Kousha; Immerman, Neil
3
1994
Interpreting logics of knowledge in propositional dynamic logic. Zbl 0634.03012
Fischer, Michael J.; Immerman, Neil
3
1987
Decentralizing SDN policies. Zbl 1346.68027
Padon, Oded; Immerman, Neil; Karbyshev, Aleksandr; Lahav, Ori; Sagiv, Mooly; Shoham, Sharon
2
2015
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
2
2005
Number of variables is equivalent to space. Zbl 0986.68040
Immerman, Neil; Buss, Jonathan F.; Barrington, David A. Mix
2
2001
Descriptive and computational complexity. Zbl 0675.68032
Immerman, Neil
2
1989
Finding reductions automatically. Zbl 1287.68024
Crouch, Michael; Immerman, Neil; Moss, J. Eliot B.
1
2010
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
Structure theorem and strict alternation hierarchy for FO\(^{2}\) on words. Zbl 1168.03328
Weis, P.; Immerman, N.
1
2007
Decentralizing SDN policies. Zbl 1346.68027
Padon, Oded; Immerman, Neil; Karbyshev, Aleksandr; Lahav, Ori; Sagiv, Mooly; Shoham, Sharon
2
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
3
2014
Applicability conditions for plans with loops: computability results and algorithms. Zbl 1270.68277
Srivastava, Siddharth; Immerman, Neil; Zilberstein, Shlomo
3
2012
Experimental descriptive complexity. Zbl 1354.68103
Carmosino, Marco; Immerman, Neil; Jordan, Charles
3
2012
A new representation and associated algorithms for generalized planning. Zbl 1216.68253
Srivastava, Siddharth; Immerman, Neil; Zilberstein, Shlomo
5
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
11
2009
Structure theorem and strict alternation hierarchy for FO\(^{2}\) on words. Zbl 1168.03019
Weis, Philipp; Immerman, Neil
7
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
21
2008
Structure theorem and strict alternation hierarchy for FO\(^{2}\) on words. Zbl 1168.03328
Weis, P.; Immerman, N.
1
2007
The complexity of satisfiability problems: Refining Schaefer’s theorem. Zbl 1156.68396
Allender, Eric; Bauland, Michael; Immerman, Neil; Schnoor, Henning; Vollmer, Heribert
11
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.
5
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
2
2005
The boundary between decidability and undecidability for transitive-closure logics. Zbl 1095.03008
Immerman, Neil; Rabinovich, Alex; Reps, Tom; Sagiv, Mooly; Yorsh, Greta
11
2004
Verification via structure simulation. Zbl 1103.68623
Immerman, Niel; Rabinovich, Alexander; Reps, Thomas W.; Sagiv, Mooly; Yorsh, Great
4
2004
An \(n!\) lower bound on formula size. Zbl 1365.68270
Adler, Micah; Immerman, Neil
9
2003
The complexity of decentralized control of Markov decision processes. Zbl 1082.90593
Bernstein, Daniel S.; Givan, Robert; Immerman, Neil; Zilberstein, Shlomo
24
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
6
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
101
1999
Progress in descriptive complexity. Zbl 0959.68523
Immerman, Neil
20
1999
Descriptive complexity and model checking. Zbl 0945.03546
Immerman, Neil
34
1998
Dyn-FO: A parallel, dynamic complexity class. Zbl 0889.68063
Patnaik, Sushant; Immerman, Neil
9
1997
Time, hardware, and uniformity. Zbl 0880.68037
Barrington, David Mix; Immerman, Neil
6
1997
A first-order isomorphism theorem. Zbl 0874.68124
Allender, Eric; Balcázar, José; Immerman, Neil
4
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.
15
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
6
1993
An optimal lower bound on the number of variables for graph identification. Zbl 0785.68043
Cai, Jin-Yi; Fürer, Martin; Immerman, Neil
72
1992
On uniformity within \(NC^ 1\). Zbl 0719.68023
Barrington, David A. Mix; Immerman, Neil; Straubing, Howard
104
1990
Expressibility and parallel complexity. Zbl 0688.68038
Immerman, Neil
33
1989
Definability with bounded number of bound variables. Zbl 0711.03004
Immerman, Neil; Kozen, Dexter
31
1989
Descriptive and computational complexity. Zbl 0756.68041
Immerman, Neil
14
1989
Relativizing relativized computations. Zbl 0679.68084
Immerman, Neil; Mahaney, Stephen R.
5
1989
Descriptive and computational complexity. Zbl 0675.68032
Immerman, Neil
2
1989
Nondeterministic space is closed under complementation. Zbl 0668.68056
Immerman, Neil
186
1988
Languages that capture complexity classes. Zbl 0634.68034
Immerman, Neil
133
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
124
1986
Sparse sets in NP-P: EXPTIME versus NEXPTIME. Zbl 0586.68042
Hartmanis, J.; Immerman, N.; Sewelson, V.
43
1985
On complete problems for \(NP\cap C_ 0NP\). Zbl 0576.68032
Hartmanis, Juris; Immerman, Neil
6
1985
Upper and lower bounds for first order expressibility. Zbl 0503.68032
Immerman, Neil
52
1982
Number of quantifiers is better than number of tape cells. Zbl 0486.03019
Immerman, Neil
45
1981
all top 5

Cited by 1,075 Authors

19 Allender, Eric W.
18 Vollmer, Heribert
17 Grohe, Martin
17 Stewart, Iain A.
16 Immerman, Neil
14 Geffert, Viliam
12 Hemaspaandra, Lane A.
12 Kolaitis, Phokion G.
11 Chatterjee, Krishnendu
11 Hella, Lauri T.
11 Holzer, Markus
11 McKenzie, Pierre
11 Verbitsky, Oleg
10 Dawar, Anuj
10 Krebs, Andreas
10 Mix Barrington, David A.
10 Vardi, Moshe Y.
10 Vianu, Victor
9 Libkin, Leonid O.
9 Schwentick, Thomas
9 Thérien, Denis
8 Grädel, Erich
8 Henzinger, Thomas A.
8 Kufleitner, Manfred
7 Jenner, Birgit
7 Köbler, Johannes
7 Ogihara, Mitsunori
7 Schweikardt, Nicole
7 Tantau, Till
7 Turull Torres, Jose Maria
6 Abiteboul, Serge
6 Flum, Jörg
6 Makowsky, Johann-Andreas
6 Otto, Martin
6 Straubing, Howard
6 Van den Bussche, Jan
5 Agrawal, Manindra
5 Àlvarez, Carme
5 Arvind, Vikraman
5 Atserias, Albert
5 Cai, Jin-Yi
5 Cook, Stephen Arthur
5 Datta, Samir
5 Durand, Arnaud
5 Gottlob, Georg
5 Grandjean, Etienne
5 Huynh, Dung T.
5 Ibarra, Oscar H.
5 Jakobi, Sebastian
5 Kontinen, Juha
5 Kupferman, Orna
5 Lautemann, Clemens
5 Meinel, Christoph
5 Okhotin, Alexander
5 Rabinovich, Alexander
5 Szepietowski, Andrzej
5 Wong, Limsoon
5 Zhukovskii, Maxim Evgenievich
4 Balcázar, José Luis
4 Beigel, Richard
4 Benedikt, Michael A.
4 Chen, Hubie
4 Chen, Yijia
4 Compton, Kevin J.
4 de Rijke, Maarten
4 Etessami, Kousha
4 Fleischer, Lukas
4 Grumbach, Stéphane
4 Halpern, Joseph Yehuda
4 Lohrey, Markus
4 Mandrioli, Dino
4 Martins, Ana Teresa
4 McColm, Gregory L.
4 Mundhenk, Martin
4 Péladeau, Pierre
4 Pighizzini, Giovanni
4 Pikhurko, Oleg
4 Pradella, Matteo
4 Raskin, Jean-François
4 Sagiv, Mooly
4 Schnoor, Henning
4 Segoufin, Luc
4 Silvestri, Riccardo
4 Suciu, Dan Mircea
4 Thierauf, Thomas
4 Van Gucht, Dirk
4 Veith, Helmut
4 Wächter, Jan Philipp
4 Zeume, Thomas
3 Arenas, Marcelo
3 Babai, László
3 Behle, Christoph
3 Berkholz, Christoph
3 Blass, Andreas Raphael
3 Bollig, Benedikt
3 Borchert, Bernd
3 Bournez, Olivier
3 Buhrman, Harry
3 Chen, Jian-er
3 Cho, Sang
...and 975 more Authors
all top 5

Cited in 98 Serials

154 Theoretical Computer Science
81 Information and Computation
77 Journal of Computer and System Sciences
39 Information Processing Letters
33 Theory of Computing Systems
27 Annals of Pure and Applied Logic
25 The Journal of Symbolic Logic
18 Artificial Intelligence
17 Computational Complexity
16 Logical Methods in Computer Science
15 International Journal of Foundations of Computer Science
13 Acta Informatica
13 Annals of Mathematics and Artificial Intelligence
12 Mathematical Systems Theory
11 RAIRO. Informatique Théorique et Applications
9 ACM Transactions on Computational Logic
8 The Bulletin of Symbolic Logic
7 Studia Logica
7 Mathematical Logic Quarterly (MLQ)
5 Discrete Applied Mathematics
5 Journal of Symbolic Computation
5 Archive for Mathematical Logic
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 Computing
4 European Journal of Combinatorics
4 Journal of Automated Reasoning
4 International Journal of Algebra and Computation
4 MSCS. Mathematical Structures in Computer Science
4 Journal of Applied Logic
3 Algebra Universalis
3 Information Sciences
3 Algorithmica
3 Formal Aspects of Computing
3 The Journal of Artificial Intelligence Research (JAIR)
3 Computer Science Review
2 Journal of Combinatorial Theory. Series A
2 Journal of Combinatorial Theory. Series B
2 Journal of Philosophical Logic
2 Journal of Complexity
2 International Journal of Approximate Reasoning
2 Annals of Operations Research
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 International Journal of Parallel, Emergent and Distributed Systems
1 Computers & Mathematics with Applications
1 Journal of Statistical Physics
1 Problems of Information Transmission
1 Automatica
1 International Journal of Game Theory
1 Journal of Graph Theory
1 Journal of Mathematical Psychology
1 Journal of Pure and Applied Algebra
1 Operations Research
1 Semigroup Forum
1 Synthese
1 Advances in Applied Mathematics
1 Ergodic Theory and Dynamical Systems
1 Mathematical Social Sciences
1 Combinatorica
1 Journal of Computer Science and Technology
1 New Generation Computing
1 JETAI. Journal of Experimental & Theoretical Artificial Intelligence
1 Linear Algebra and its Applications
1 Distributed Computing
1 Advances in Applied Clifford Algebras
1 Acta Mathematica et Informatica Universitatis Ostraviensis
1 Doklady Mathematics
1 Soft Computing
1 Journal of Graph Algorithms and Applications
1 Journal of the ACM
1 Mathematical and Computer Modelling of Dynamical Systems
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
1 Theory and Practice of Logic Programming
1 Journal of Machine Learning Research (JMLR)
1 Natural Computing
1 Journal of Discrete Algorithms
1 Discrete Optimization
1 Proceedings of the Steklov Institute of Mathematics
1 Algorithms
1 Journal of the Brazilian Computer Society
1 RAIRO. Theoretical Informatics and Applications
1 Bulletin of Mathematical Sciences
1 Frontiers of Computer Science
1 Forum of Mathematics, Sigma
1 Axioms
1 ACM Transactions on Computation Theory
1 Journal of Combinatorial Algebra

Citations by Year

Wikidata Timeline

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