Papers of Klaus-Jörn Lange

Ch. Behle und K.-J. Lange.
FO[<]-Uniformity
Akzeptiert auf der CCC 2006
B. Borchert, K.-J. Lange, F. Stephan, P. Tesson und D. Thérien.
The Dot-Depth and the Polynomial Hierarchies Correspond on the Delta Levels
Int. Journal of Foundations of Computer Science, 16(4): 625-644 (2005).
A. Krebs, K.-J. Lange und St. Reifferscheid.
Characterizing TC0 in terms of Infinite Groups.
Proc. of the 22nd STACS 2005,LNCS 3404, pages 496-507,2005.
Akzeptiert zur Veröffentlichung in Theory of Computing Systems.
K.-J. Lange.
Some Results on Majority Quantifiers over Words.
In 19th IEEE Conference on Computational Complexity, pages 123-129, 2004.
D. Barrington, P. Kadau, K.-J. Lange und P. McKenzie.
On the complexity of some problems on groups input as multiplication tables.
Journal of Computer and System Sciences, 63(2): 186-200 (2001)
D. Barrington, P. Kadau, K.-J. Lange und P. McKenzie.
On the complexity of some problems on groups input as multiplication tables.
In 15th IEEE Conference on Computational Complexity, pages 62-69, 2000.
K.-J. Lange, P. McKenzie, und A. Tapp.
Reversible space equals deterministic space.
Journal of Computer and System Sciences, 60:354-367, 2000.
K.-J. Lange und R. Niedermeier
Data-independences of read, write, and control structures in pram computations.
Journal of Computer and System Sciences, 60:109-144, 2000.
E. Allender and K.-J. Lange
RUSPACE(log n) in DSPACE(log²(n) / log(log(n)))
Theory of Computing Systems 31 539-550, 1998.
K.-J. Lange and P. McKenzie
On the complexity of free monoid morphisms
ISAAC'98, number 1533 in LNCS, pages 247-256. Springer Verlag, 1998.
K.-J. Lange
On the distributed realization of parallel algorithms
SOFSEM'97: Theory and Practice of Informtics,, number 1338 in LNCS, pages 37-52. Springer-Verlag, 1997.
K.-J. Lange, P. McKenzie and A. Tapp
Reversible Space Equals Deterministic Space
In 12th IEEE Conference on Computational Complexity, pages 45 50, 1997.
M. Holzer and K.-J. Lange:
On the Complexity of Iterated Insertions
In G. Paun and A. Salomaa, editors, Trends in Formal Languages, Springer LNCS 1218 (1997), 440-453.
K.-J. Lange:
An unambiguous class possessing a complete Set
STACS'97, number 1200 in LNCS, pages339-350. Springer-Verlag, 1997.
K.-J. Lange
Are there formal languages complete for SymSPACE(log n)?.
In Foundations of Computer Science: Potential-Theorie-Cognition, number 1337 in LNCS, pages 125-134. Springer-Verlag, 1996.
E. Allender and K.-J. Lange:
StUSPACE(log(n)) in DSPACE(log²(n) / log(log(n))).
In T. Asano, Y. Jgarashi, N. Nagamochi, S. Miyano, and S. Suri, editors, 7th international Symposium on Algorithms and Computation, ISAAC '96, volume 1178 of LNCS, pages 193-202, Osaka, Japan, December 1996. Springer Verlag. also see Electronic Colloquium on Computational Complexity, Report TR96-048, available via http://www.eccc.uni-trier.de/eccc/
H. Fernau, K.-J. Lange and K. Reinhardt:
Advocating ownership
In V. Chandru, editor, Proceedings of the 16th Conferencce on Foundations of Software Technology and Theoretical Compter Science Springer LNCS 1180 (1996), 286-297.
K.-J. Lange:
Complexity and structure in formal language theory.
Fundamenta Informaticae, 25(3) 327-352, 1996.
K.-J. Lange and K. Reinhardt:
Set automata
In D. S. Bridges, C. Calude, J. Gibbons, S. Reeves and L. Witten, editors, Combinatorics, Complexity, Logic, Proceedings of DMTCS '96,
pages 321-329. Springer Verlag 1996.
Y. Ben-Asher, K.-J. Lange, D. Peleg and A. Schuster
The Complexity of Reconfiguring Network Models
In Information and Computation, 121 41-58, 1995.
K.-J. Lange and K. Reinhardt:
Empty Alternation,
MFCS'94, Springer LNCS 841 (1994), 494-503.
K.-J. Lange and P. Rossmanith:
Unambiguous polynomial hierarchies and exponential size
Structures'94 IEEE Computer Society Press 5670 (1994), 106-115.
C. Damm, M. Holzer, K.-J. Lange, and P. Rossmanith:
Deterministic 0L languages are of very low complexity: D0L is in AC^0
Proc. of Developments in Language Theory, World Scientific, Singapore (1994), 305-313.
K.-J. Lange and R. Niedermeier:
Data-independence of Parallel Random Access Machines
FST\&TCS'93 Springer LNCS 761 (1993), 104-113.
M. Holzer and K.-J. Lange:
On the complexity of linear LL(1) and LR(1) grammars
FCT'93 Springer LNCS 710 (1993), 299-308.
K.-J. Lange:
Complexity and structure in formal language theory
Structures'93, IEEE Computer Society Press 4070 (1993), 224-238.
K.-J. Lange:
Unambiguity of Circuits,
Theoret. Comput. Sci. 107 (1993), 77-94.
K.-J. Lange and P. Rossmanith:
The emptiness problem for intersections of regular languages
MFCS'92 Springer LNCS 629 (1992), 346-354.
C. Damm, M. Holzer and K.-J. Lange:
Parallel complexity of iterated morphisms and the arithmetic of small numbers
MFCS'92 Springer LNCS 629 (1992), 227-235.
K.-J. Lange, P. Rossmanith and W. Rytter:
Parallel recognition and ranking of context-free languages
MFCS'92 eingeladener Vortrag, Springer LNCS 629 (1992), 24-36.
J. Dassow and K.-J. Lange:
Computational complexity and hardest languages of automata with abstract storages
FCT'91 Springer LNCS 529 (1991), 200-209.
G. Buntrock, B. Jenner, K.-J. Lange, P. Rossmanith:
Unambiguity and fewness for logarithmic space
FCT'91 Springer LNCS 529 (1991), 178-189.
D. Gomm, M. Heckner, K.-J. Lange and G. Riedle:
On the design of parallel programs for machines with distributed memory
EDMCC2 Springer LNCS 487 (1991), 381-391.
K.-J. Lange and P. Rossmanith:
Characterizing unambiguous augmented pushdown automata by circuits
MFCS'90 Springer LNCS 452 (1990), 399-406.
M. Jantzen, M. Kudlek, K.-J. Lange and H Petersen:
Dyck₁-Reductions of context-free Languages,
Comp. and Artif. Intel. 9 (1990), 3-18.
K.-J. Lange:
Unambiguity of circuits
Structures'90 IEEE Computer Society Press 2072 (1990), 130-137.
B. Jenner, B. Kirsig and K.-J. Lange:
The logarithmic alternation hierarchy collapses: $A\Sigma_2^{\cal L} = A\Pi_2^{\cal L}$},
Information and Computation 80 (1989), 269-287.
K.-J. Lange:
Decompositions of nondeterministic reductions,
Theoret. Comput. Sci. 58 (1988), 175-181.
K.-J. Lange:
Complexity theory and formal languages
IMYCS'88 eingeladener Vortrag, Ungarische Akademie der Wissenschaften, Tanulmányok 208 (1988), 37-54, und Springer LNCS 381 (1989), 19-36.
K.-J. Lange, B. Jenner and B. Kirsig:
The logarithmic alternation hierarchy collapses
ICALP'87 Springer LNCS 267 (1987), 531-541.
M. Jantzen, M. Kudlek, K.-J. Lange and H. Petersen:
Dyck₁-reductions of context-free languages
FCT'87 Kazan (1987).
B. Kirsig and K.-J. Lange:
Separation with the Ruzzo, Simon, and Tompa-relativization implies DSPACE(log n) != NSPACE(log n),
Inform. Proc. Lett. 25 (1987), 13-15.
K.-J. Lange and E. Welzl:
String grammars with disconnecting or on a basic root of the difficulty in graph grammar parsing,
Discr. Appl. Math 16 (1987), 17-30.
K.-J. Lange:
Two characterizations of the logarithmic alternation hierarchy
MFCS'86 Springer LNCS 233 (1986), 518-526.
K.-J. Lange:
Decompositions of nondeterministic reductions
ICALP'86 Springer LNCS 226 (1986), 206-214.
K.-J. Lange and E. Welzl:
String grammars with disconnecting
FCT'85 Springer LNCS 199 (1985), 249-256.
W. Brauer and K.-J. Lange:
Nondeterministic twotape automata are more powerful than deterministic ones
STACS'85 Springer LNCS 182 (1985), 71-79.
K.-J. Lange and E. Welzl:
Recurrent words and simultaneous growth in TOL systems,
Theoret. Comput. Sci. 35 (1985), 1-15.
K.-J. Lange:
DTOL systems and catenativity,
Elektron. Informationsverarb. und Kybernetik 20 (1984), 81-92.
T. Yokomori, D. Wood and K.-J. Lange:
A three-restricted normal form theorem for ETOL languages,
Inform. Proc. Lett. 14 (1982), 97-100 und Erratum in Inform. Proc. Lett. 17 (1985), 100.
K.-J. Lange:
Nondeterministic logspace reductions
MFCS'84 Springer LNCS 176 (1984), 378-388.
K.-J. Lange:
Context-free controlled ET0L systems
ICALP'83 Springer LNCS 154 (1983), 723-733.
K.-J Lange:
L homomorphisms and reductions of 0L systems,
Internat. J. Comput. Math. 11 Sec. A (1982), 197-205.
K.-J. Lange:
Equivalence of adult languages and extensions for DT0L systems,
Information and Control 47 (1980), 107-112.

Last update September 5th, 1998

Letzte Änderung: 28. Mar. ‘06 | Bei Fragen und Anregungen E-Mail an: Klaus-Jörn Lange