×
Author ID: lange.klaus-jorn Recent zbMATH articles by "Lange, Klaus-Jörn"
Published as: Lange, Klaus-Jörn; Lange, K.-J.; Lange, Klaus-Joern
External Links: MGP · dblp · GND
Documents Indexed: 55 Publications since 1980
Biographic References: 1 Publication
Co-Authors: 38 Co-Authors with 40 Joint Publications
1,373 Co-Co-Authors

Publications by Year

Citations contained in zbMATH Open

42 Publications have been cited 225 times in 186 Documents Cited by Year
Reversible space equals deterministic space. Zbl 0956.68057
Lange, Klaus-Jörn; McKenzie, Pierre; Tapp, Alain
39
2000
On the complexities of linear LL(1) and LR(1) grammars. Zbl 0794.68085
Holzer, Markus; Lange, Klaus-Jörn
17
1993
Unambiguity and fewness for logarithmic space. Zbl 0925.68184
Buntrock, Gerhard; Jenner, Birgit; Lange, Klaus-Jörn; Rossmanith, Peter
14
1991
The emptiness problem for intersections of regular languages. Zbl 1493.68191
Lange, Klaus-Jörn; Rossmanith, Peter
12
1992
String grammars with disconnecting or a basic root of the difficulty in graph grammar parsing. Zbl 0619.68064
Lange, Klaus-Jörn; Welzl, Emo
10
1987
On the complexity of free monoid morphisms. Zbl 0930.68081
Lange, Klaus-Jörn; McKenzie, Pierre
10
1998
On the complexity of some problems on groups input as multiplication tables. Zbl 0988.68080
Barrington, David Mix; Kadau, Peter; Lange, Klaus-Jörn; McKenzie, Pierre
8
2001
Characterizing \(\text{TC}^{0}\) in terms of infinite groups. Zbl 1121.68075
Krebs, Andreas; Lange, Klaus-Jörn; Reifferscheid, Stephanie
8
2007
A three-restricted normal form theorem for ETOL languages. Zbl 0483.68068
Yokomori, Takashi; Wood, Derick; Lange, Klaus-Joern
7
1982
Unambiguity of circuits. Zbl 0774.68047
Lange, Klaus-Jörn
7
1993
The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^{{\mathcal L}}=A\Pi_ 2^{{\mathcal L}}\). Zbl 0668.68055
Jenner, Birgit; Kirsig, Bernd; Lange, Klaus-Jörn
6
1989
Separation with the Ruzzo, Simon, and Tompa relativization implies DSPACE(log n)\(\neq NSPACE(\log \,n)\). Zbl 0629.68050
Kirsig, Bernd; Lange, Klaus-Jörn
5
1987
Computational complexity and hardest languages of automata with abstract storages. Zbl 0925.03182
Dassow, Jürgen; Lange, Klaus-Jörn
5
1991
Set automata. Zbl 0914.68117
Lange, Klaus-Jörn; Reinhardt, Klaus
5
1997
Deciding regular intersection emptiness of complete problems for PSPACE and the polynomial hierarchy. Zbl 1504.68102
Güler, Demen; Krebs, Andreas; Lange, Klaus-Jörn; Wolf, Petra
5
2018
Characterizing unambiguous augmented pushdown automata by circuits. Zbl 0731.68038
Lange, Klaus-Jörn; Rossmanith, Peter
5
1990
Two characterizations of the logarithmic alternation hierarchy. Zbl 0616.68050
Lange, Klaus-Jörn
4
1986
The complexity of reconfiguring network models. Zbl 0832.68045
Ben-Asher, Y.; Lange, K.-J.; Peleg, D.; Schuster, A.
4
1995
Characterizing TC\(^{0}\) in terms of infinite groups. Zbl 1119.68090
Krebs, Andreas; Lange, Klaus-Jörn; Reifferscheid, Stephanie
4
2005
An unambiguous class possessing a complete set. Zbl 1498.68116
Lange, Klaus-Jörn
4
1997
The logarithmic alternation hierarchy collapses: \(A\Sigma_ 2^{\mathfrak L}=A\Pi_ 2^{\mathfrak L}\). Zbl 0629.68051
Lange, Klaus-Jörn; Jenner, Birgit; Kirsig, Bernd
3
1987
Dyc\(k_ 1\)-reductions of context-free languages. Zbl 0642.68134
Jantzen, Matthias; Kudlek, Manfred; Lange, Klaus-Jörn; Petersen, Holger
3
1987
The complexity of the emptiness problem for E0L systems. Zbl 0769.68064
Lange, Klaus-Jörn; Schudy, Michael
3
1992
Visibly counter languages and constant depth circuits. Zbl 1355.68163
Krebs, Andreas; Lange, Klaus-Jörn; Ludwig, Michael
3
2015
Context-free controlled ETOL systems. Zbl 0521.68088
Lange, Klaus-Joern
3
1983
Visibly counter languages and the structure of \(\mathrm {NC}^{1}\). Zbl 1465.68078
Hahn, Michael; Krebs, Andreas; Lange, Klaus-Jörn; Ludwig, Michael
3
2015
A note on the P-completeness of deterministic one-way stack language. Zbl 1216.68146
Lange, K.-J.
3
2010
Non-deterministic two-tape automata are more powerful than deterministic ones. Zbl 0604.68093
Brauer, W.; Lange, K.-J.
3
1985
\(\mathrm{RUSPACE}(\log n)\subseteq \mathrm{DSPACE}(\log^2n/\log \log n)\). Zbl 0910.68007
Allender, E.; Lange, K.-J.
3
1998
The dot-depth and the polynomial hierarchies correspond on the delta levels. Zbl 1161.68512
Borchert, Bernd; Lange, Klaus-Jörn; Stephan, Frank; Tesson, Pascal; Thérien, Denis
3
2005
Nondeterministic logspace reductions. Zbl 0567.03016
Lange, Klaus-Jörn
3
1984
Complexity and structure in formal language theory. Zbl 0843.68053
Lange, Klaus-Jörn
2
1996
Erratum to: “A three-restricted normal form theorem for ETOL languages. Zbl 0571.68060
Yokomori, Takashi; Wood, Derick; Lange, Klaus-Jörn
2
1985
L homomorphisms and reductions of OL systems. Zbl 0485.68069
Lange, Klaus-Joern
1
1982
A further link between formal languages and complexity theory. Zbl 0663.68060
Lange, Klaus-Jörn; Schudy, Michael
1
1987
The dot-depth and the polynomial hierarchy correspond on the Delta levels. Zbl 1117.68393
Borchert, Bernd; Lange, Klaus-Jörn; Stephan, Frank; Tesson, Pascal; Thérien, Denis
1
2004
The lower reaches of circuit uniformity. Zbl 1365.68263
Behle, Christoph; Krebs, Andreas; Lange, Klaus-Jörn; McKenzie, Pierre
1
2012
Dense completeness. Zbl 1370.68182
Krebs, Andreas; Lange, Klaus-Jörn
1
2012
Decompositions of nondeterministic reductions. Zbl 0596.68043
Lange, Klaus-Jörn
1
1986
Symmetry coincides with nondeterminism for time-bounded auxiliary pushdown automata. Zbl 1366.68068
Allender, Eric; Lange, Klaus-Jörn
1
2014
Parallel complexity of iterated morphisms and the arithmetic of small numbers. Zbl 1493.68186
Damm, Carsten; Holzer, Markus; Lange, Klaus-Jörn
1
1992
Empty alternation. Zbl 1493.68151
Lange, Klaus-Jörn; Reinhardt, Klaus
1
1994
Deciding regular intersection emptiness of complete problems for PSPACE and the polynomial hierarchy. Zbl 1504.68102
Güler, Demen; Krebs, Andreas; Lange, Klaus-Jörn; Wolf, Petra
5
2018
Visibly counter languages and constant depth circuits. Zbl 1355.68163
Krebs, Andreas; Lange, Klaus-Jörn; Ludwig, Michael
3
2015
Visibly counter languages and the structure of \(\mathrm {NC}^{1}\). Zbl 1465.68078
Hahn, Michael; Krebs, Andreas; Lange, Klaus-Jörn; Ludwig, Michael
3
2015
Symmetry coincides with nondeterminism for time-bounded auxiliary pushdown automata. Zbl 1366.68068
Allender, Eric; Lange, Klaus-Jörn
1
2014
The lower reaches of circuit uniformity. Zbl 1365.68263
Behle, Christoph; Krebs, Andreas; Lange, Klaus-Jörn; McKenzie, Pierre
1
2012
Dense completeness. Zbl 1370.68182
Krebs, Andreas; Lange, Klaus-Jörn
1
2012
A note on the P-completeness of deterministic one-way stack language. Zbl 1216.68146
Lange, K.-J.
3
2010
Characterizing \(\text{TC}^{0}\) in terms of infinite groups. Zbl 1121.68075
Krebs, Andreas; Lange, Klaus-Jörn; Reifferscheid, Stephanie
8
2007
Characterizing TC\(^{0}\) in terms of infinite groups. Zbl 1119.68090
Krebs, Andreas; Lange, Klaus-Jörn; Reifferscheid, Stephanie
4
2005
The dot-depth and the polynomial hierarchies correspond on the delta levels. Zbl 1161.68512
Borchert, Bernd; Lange, Klaus-Jörn; Stephan, Frank; Tesson, Pascal; Thérien, Denis
3
2005
The dot-depth and the polynomial hierarchy correspond on the Delta levels. Zbl 1117.68393
Borchert, Bernd; Lange, Klaus-Jörn; Stephan, Frank; Tesson, Pascal; Thérien, Denis
1
2004
On the complexity of some problems on groups input as multiplication tables. Zbl 0988.68080
Barrington, David Mix; Kadau, Peter; Lange, Klaus-Jörn; McKenzie, Pierre
8
2001
Reversible space equals deterministic space. Zbl 0956.68057
Lange, Klaus-Jörn; McKenzie, Pierre; Tapp, Alain
39
2000
On the complexity of free monoid morphisms. Zbl 0930.68081
Lange, Klaus-Jörn; McKenzie, Pierre
10
1998
\(\mathrm{RUSPACE}(\log n)\subseteq \mathrm{DSPACE}(\log^2n/\log \log n)\). Zbl 0910.68007
Allender, E.; Lange, K.-J.
3
1998
Set automata. Zbl 0914.68117
Lange, Klaus-Jörn; Reinhardt, Klaus
5
1997
An unambiguous class possessing a complete set. Zbl 1498.68116
Lange, Klaus-Jörn
4
1997
Complexity and structure in formal language theory. Zbl 0843.68053
Lange, Klaus-Jörn
2
1996
The complexity of reconfiguring network models. Zbl 0832.68045
Ben-Asher, Y.; Lange, K.-J.; Peleg, D.; Schuster, A.
4
1995
Empty alternation. Zbl 1493.68151
Lange, Klaus-Jörn; Reinhardt, Klaus
1
1994
On the complexities of linear LL(1) and LR(1) grammars. Zbl 0794.68085
Holzer, Markus; Lange, Klaus-Jörn
17
1993
Unambiguity of circuits. Zbl 0774.68047
Lange, Klaus-Jörn
7
1993
The emptiness problem for intersections of regular languages. Zbl 1493.68191
Lange, Klaus-Jörn; Rossmanith, Peter
12
1992
The complexity of the emptiness problem for E0L systems. Zbl 0769.68064
Lange, Klaus-Jörn; Schudy, Michael
3
1992
Parallel complexity of iterated morphisms and the arithmetic of small numbers. Zbl 1493.68186
Damm, Carsten; Holzer, Markus; Lange, Klaus-Jörn
1
1992
Unambiguity and fewness for logarithmic space. Zbl 0925.68184
Buntrock, Gerhard; Jenner, Birgit; Lange, Klaus-Jörn; Rossmanith, Peter
14
1991
Computational complexity and hardest languages of automata with abstract storages. Zbl 0925.03182
Dassow, Jürgen; Lange, Klaus-Jörn
5
1991
Characterizing unambiguous augmented pushdown automata by circuits. Zbl 0731.68038
Lange, Klaus-Jörn; Rossmanith, Peter
5
1990
The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^{{\mathcal L}}=A\Pi_ 2^{{\mathcal L}}\). Zbl 0668.68055
Jenner, Birgit; Kirsig, Bernd; Lange, Klaus-Jörn
6
1989
String grammars with disconnecting or a basic root of the difficulty in graph grammar parsing. Zbl 0619.68064
Lange, Klaus-Jörn; Welzl, Emo
10
1987
Separation with the Ruzzo, Simon, and Tompa relativization implies DSPACE(log n)\(\neq NSPACE(\log \,n)\). Zbl 0629.68050
Kirsig, Bernd; Lange, Klaus-Jörn
5
1987
The logarithmic alternation hierarchy collapses: \(A\Sigma_ 2^{\mathfrak L}=A\Pi_ 2^{\mathfrak L}\). Zbl 0629.68051
Lange, Klaus-Jörn; Jenner, Birgit; Kirsig, Bernd
3
1987
Dyc\(k_ 1\)-reductions of context-free languages. Zbl 0642.68134
Jantzen, Matthias; Kudlek, Manfred; Lange, Klaus-Jörn; Petersen, Holger
3
1987
A further link between formal languages and complexity theory. Zbl 0663.68060
Lange, Klaus-Jörn; Schudy, Michael
1
1987
Two characterizations of the logarithmic alternation hierarchy. Zbl 0616.68050
Lange, Klaus-Jörn
4
1986
Decompositions of nondeterministic reductions. Zbl 0596.68043
Lange, Klaus-Jörn
1
1986
Non-deterministic two-tape automata are more powerful than deterministic ones. Zbl 0604.68093
Brauer, W.; Lange, K.-J.
3
1985
Erratum to: “A three-restricted normal form theorem for ETOL languages. Zbl 0571.68060
Yokomori, Takashi; Wood, Derick; Lange, Klaus-Jörn
2
1985
Nondeterministic logspace reductions. Zbl 0567.03016
Lange, Klaus-Jörn
3
1984
Context-free controlled ETOL systems. Zbl 0521.68088
Lange, Klaus-Joern
3
1983
A three-restricted normal form theorem for ETOL languages. Zbl 0483.68068
Yokomori, Takashi; Wood, Derick; Lange, Klaus-Joern
7
1982
L homomorphisms and reductions of OL systems. Zbl 0485.68069
Lange, Klaus-Joern
1
1982
all top 5

Cited by 222 Authors

16 Kutrib, Martin
14 Lange, Klaus-Jörn
12 Krebs, Andreas
10 Malcher, Andreas
9 Fernau, Henning
9 Holzer, Markus
8 Wendlandt, Matthias
7 Allender, Eric W.
7 Okhotin, Alexander
6 Drewes, Frank
5 Limaye, Nutan
5 McKenzie, Pierre
5 Weiß, Armin
4 Bordihn, Henning
4 Dassow, Jürgen
4 Jenner, Birgit
4 Lavado, Giovanna Janet
4 Lohrey, Markus
4 Ludwig, Michael
4 Mahajan, Meena
4 Myasnikov, Alexei G.
4 Prigioniero, Luca
4 Rossmanith, Peter
4 Wolf, Petra
3 Behle, Christoph
3 Cadilhac, Michaël
3 Geffert, Viliam
3 Glaßer, Christian
3 Hoffmann, Berthold
3 Kirsig, Bernd
3 Meyer, Uwe
3 Morita, Kenichi
3 Pighizzini, Giovanni
3 Reinhardt, Klaus
3 Tewari, Raghunath
3 Vogler, Heiko
2 Axelsen, Holger Bock
2 Bourgeois, Anu G.
2 Damm, Carsten
2 Datta, Samir
2 de Rezende, Susanna F.
2 Diekert, Volker
2 Engelfriet, Joost
2 Fleischer, Lukas
2 Ganardi, Moses
2 Gelle, Kitti
2 Glück, Robert
2 Iván, Szabolcs
2 Kim, Changwook
2 Meir, Or
2 Minas, Mark
2 Niedermeier, Rolf
2 Nordström, Jakob
2 Olkhovsky, Ilya
2 Otto, Friedrich
2 Pavan, Aduri
2 Raghavendra Rao, B. V.
2 Reifferscheid, Stephanie
2 Robere, Robert
2 Rubtsov, Alexander A.
2 Rytter, Wojciech
2 Salomaa, Kai T.
2 Vassileva, Svetla
2 Vinodchandran, N. Variyam
2 Vollmer, Heribert
2 Vyalyĭ, Mikhail Nikolaevich
2 Wehar, Michael
2 Wood, Derick
2 Yokoyama, Tetsuo
2 Yu, Sheng
2 Zetzsche, Georg
1 Aalbersberg, Ijsbrand Jan
1 Àlvarez, Carme
1 Arvind, Vikraman
1 Aubert, Clément
1 Babu, Ajesh
1 Bagnol, Marc
1 Baum, Eric B.
1 Beaudry, Martin
1 Beier, Simon
1 Bhatia, Amandeep Singh
1 Björklund, Henrik
1 Blondin, Michael
1 Böhler, Elmar
1 Borlido, Célia
1 Bruchertseifer, Jens
1 Bruda, Stefan D.
1 Buntrock, Gerhard
1 Buss, Samuel R.
1 Cantero, Juan Carlos
1 Cárdenas-Haro, José Antonio
1 Carvalho, Andre
1 Castaño, José M.
1 Castaño, Rodrigo
1 Caussinus, Hervé
1 Chauhan, Archit
1 Choffrut, Christian
1 Courcelle, Bruno
1 Czarnetzki, Silke
1 Czumaj, Artur
...and 122 more Authors

Citations by Year