Theoretische Informatik

Prof. Klaus-Jörn Lange

E-Mail: klaus-joern.langespam prevention@uni-tuebingen.de

Raum: B122

Telefon: 07071 / 29 77567

Adresse:

Universität Tübingen
Wilhelm-Schickard-Institut für Informatik
Arbeitsbereich Theoretische Informatik/Formale Sprachen
Sand 13
D-72076 Tübingen

Sprechstunde: nach Vereinbarung

Please contact me directly and not via social networks!

Publikationen

  1. Michael Cadilhac, Andreas Krebs, K.-J. Lange: A Language-Theoretical Approach to Descriptive Complexity, DLT2016, LNCS 9840,64-76, 2016.
  2. K.-J. Lange: The Multidimensional Block Product (Dagstuhl Slides).
  3. Michael Hahn, Andreas Krebs, Klaus-Jörn Lange, and Michael Ludwig: Visibly Counter Languages and the Structure of NC1. Accepted at MFCS2015.
  4. Andreas Krebs, K.-J. Lange, Michael Ludwig: Visibly Counter Languages and Constant Depth Circuits. STACS 2015: 594-607, and Electronic Colloquium on Computational Complexity (ECCC) 21: 177 (2014).
  5. Michael Ludwig, Andreas Krebs and K.-J. Lange: On Distinguishing NC1 and NL. DLT 2015, LNCS 9168, pp 340 - 351 (accepted)
  6. E. Allender und K.-J. Lange: Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata. Proc. 25th Annual IEEE Conference on Computational Complexity, 2010, pp.172-180. Theory of Computing Volume 10, May 2014, pp. 301-318
  7. Christoph Behle, Andreas Krebs, Klaus-Jörn Lange, Pierre McKenzie: The lower reaches of circuit uniformity, MFCS 2012, LNCS 7464, pp. 590--602, Springer Heidelberg (2012)
  8. Andreas Krebs and Klaus-Jörn Lange: Dense Completeness, DLT 2012, LNCS 7410, pp. 178--189, Springer Heidelberg (2012)
  9. K.-J. Lange: The Boolean Formula Value Problem as Formal Language, Festschrift 2012, LNCS 7300, pp. 138--144. Springer, Heidelberg (2012)
  10. C. Behle, A. Krebs, K.-J. Lange, P. McKenzie: Low Uniform versions of NC1. Electonic Colloquium on Computational Complexity (ECCC) 18: 95 (2011).
  11. K.-J. Lange: A Note on the P-completeness of Deterministic One-way Stack Language. Journal of Universal Computer Science, 16(5): 795-799 (2010)
  12. V. Diekert und K.-J. Lange: Variationen über Walther von Dyck und Dyck-Sprachen. Informatik als Dialog zwischen Theorie und Anwendung, V. Diekert, K. Weicker, N.Weicker, Vieweg+Teubner; 1. ed., pages 147-154, 2009.
  13. A. Krebs, K.-J. Lange und St. Reifferscheid: Characterizing TC0 in terms of Infinite Groups. STACS 2005, LNCS 3404, pages 496-507,2005. Theory of Computing Systems, Volume 40, Number 4, June 2007 , pp. 303-325(23).
  14. Ch. Behle und K.-J. Lange: FO[<]-Uniformity. CCC 2006, pages 183-201, 2006.
  15. 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), and The Dot-Depth and the Polynomial Hierarchies Correspond on the Delta Levels. In Developments and Language Theory 2004, pages 89-101, 2004.
  16. K.-J. Lange: Some Results on Majority Quantifiers over Words. CCC 2004, pages 123-129, 2004.
  17. D. Barrington, P. Kadau, K.-J. Lange und P. McKenzie: On the complexity of some problems on groups input as multiplication tables. CCC 2000, pages 62-69, 2000. Journal of Computer and System Sciences, 63(2): 186-200 (2001).
  18. 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. Data-independence of Parallel Random Access Machines. FSTTCS'93 Springer LNCS 761 (1993), 104-113.
  19. K.-J. Lange, P. McKenzie, und A. Tapp: Reversible space equals deterministic space. CCC'97, pages 45 50, 1997. Journal of Computer and System Sciences, 60:354-367, 2000.
  20. 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.
  21. K.-J. Lange: On the distributed realization of parallel algorithms. SOFSEM'97, number 1338 in LNCS, pages 37-52. Springer-Verlag, 1997.
  22. 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.
  23. K.-J. Lange: An unambiguous class possessing a complete Set. STACS'97, number 1200 in LNCS, pages 339-350. Springer-Verlag, 1997.
  24. E. Allender and K.-J. Lange: RUSPACE(log n) in DSPACE(log2(n) / log(log(n))). Theory of Computing Systems 31 539-550, 1998. StUSPACE(log(n)) in DSPACE(log2(n) / log(log(n))). In T. Asano, Y. Jgarashi, N.Nagamochi, S. Miyano, and S. Suri, editors, ISAAC '96, volume 1178 of LNCS, pages 193-202, Osaka, Japan, December 1996. Springer Verlag, and StUSPACE(log n) is Contained in DSPACE(log2n)/loglog n). In Electronic Colloquium on Computational Complexity (ECCC) 3 (48), 1996.
  25. 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.
  26. H. Fernau, K.-J. Lange and K. Reinhardt: Advocating ownership. In V. Chandru, editor, FSTTCS'96, Springer LNCS 1180 (1996), 286-297.
  27. 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. DMTCS'96, pages 321-329. Springer Verlag 1996.
  28. K.-J. Lange: Complexity and structure in formal language theory. Fundamenta Informaticae, 25(3) 327-352, 1996. Structures'93, 4070 (1993), 224-238.
  29. 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.
  30. K.-J. Lange and K. Reinhardt: Empty Alternation, MFCS'94, Springer LNCS 841 (1994), 494-503.
  31. K.-J. Lange and P. Rossmanith: Unambiguous polynomial hierarchies and exponential size. Structures'94, IEEE Computer Society Press 5670 (1994), 106-115.
  32. C. Damm, M. Holzer, K.-J. Lange, and P. Rossmanith: Deterministic 0L languages are of very low complexity: D0L is in AC^0. DTL'94, World Scientific, Singapore (1994), 305-313.
  33. 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.
  34. K.-J. Lange: Unambiguity of Circuits, Theoret. Comput. Sci. 107 (1993), 77-94. Structures'90, IEEE Computer Society Press 2072 (1990), 130-137.
  35. K.-J. Lange and P. Rossmanith: The emptiness problem for intersections of regular languages. MFCS'92, Springer LNCS 629 (1992), 346-354.
  36. 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.
  37. 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.
  38. J. Dassow and K.-J. Lange: Computational complexity and hardest languages of automata with abstract storages. FCT'91, Springer LNCS 529 (1991), 200-209.
  39. G. Buntrock, B. Jenner, K.-J. Lange, P. Rossmanith: Unambiguity and fewness for logarithmic space. FCT'91, Springer LNCS 529 (1991), 178-189.
  40. 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.
  41. K.-J. Lange and P. Rossmanith: Characterizing unambiguous augmented pushdown automata by circuits. MFCS'90, Springer LNCS 452 (1990), 399-406.
  42. M. Jantzen, M. Kudlek, K.-J. Lange and H Petersen: Dyck1-Reductions of context-free Languages, Comp. and Artif. Intel. 9 (1990), 3-18. Dyck1-reductions of context-free languages. FCT'87, Kazan (1987).
  43. B. Jenner, B. Kirsig and K.-J. Lange: The logarithmic alternation hierarchy collapses: AΣ2L = AΠ2L, Information and Computation 80 (1989), 269-287. The logarithmic alternation hierarchy collapses. ICALP'87, Springer LNCS 267 (1987), 531-541.
  44. 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.
  45. K.-J. Lange: Decompositions of nondeterministic reductions. ICALP'86, Springer LNCS 226 (1986), 206-214, and K.-J. Lange: Decompositions of Nondeterministic Reductions. Theor. Comput. Sci. 58: 175-181 (1988).
  46. K.-J. Lange, M. Schudy: A further link between formal languages and complexity theory, Bulletin of the EATCS 33 (1987), 67-70.
  47. 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.
  48. 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.
  49. K.-J. Lange: Two characterizations of the logarithmic alternation hierarchy. MFCS'86, Springer LNCS 233 (1986), 518-526.
  50. K.-J. Lange and E. Welzl: String grammars with disconnecting. FCT'85, Springer LNCS 199 (1985), 249-256.
  51. K.-J. Lange: A note on the closure of EOL-languages under erasing homomorphisms, Bulletin of the EATCS 25 (1985), 22-23.
  52. K.-J. Lange: Addendum to "A note on the closure of EOL languages under erasing homomorphisms", Bulletin of the EATCS 26 (1985), 55.
  53. W. Brauer and K.-J. Lange: Nondeterministic twotape automata are more powerful than deterministic ones. STACS'85, Springer LNCS 182 (1985), 71-79.
  54. K.-J. Lange and E. Welzl: Recurrent words and simultaneous growth in TOL systems, Theoret. Comput. Sci. 35 (1985), 1-15.
  55. 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.
  56. K.-J. Lange: DTOL systems and catenativity, Elektron. Informationsverarb. und Kybernetik 20 (1984), 81-92.
  57. K.-J. Lange: Nondeterministic logspace reductions. MFCS'84, Springer LNCS 176 (1984), 378-388.
  58. K.-J. Lange: Context-free controlled ET0L systems. ICALP'83, Springer LNCS 154 (1983), 723-733.
  59. K.-J. Lange: L homomorphisms and reductions of 0L systems, Internat. J. Comput. Math. 11 Sec. A (1982), 197-205.
  60. K.-J. Lange: Equivalence of adult languages and extensions for DT0L systems, Information and Control 47 (1980), 107-112.