Klaus-Jörn Lange

According to our database, Klaus-Jörn Lange authored at least 67 papers between 1980 and 2018.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2018

Visibly Pushdown Languages and Free Profinite Algebras.

Silke Czarnetzki, Andreas Krebs, Klaus-Jörn Lange

CoRR, 2018

Deciding Regular Intersection Emptiness of Complete Problems for PSPACE and the Polynomial Hierarchy.

Demen Güler, Andreas Krebs, Klaus-Jörn Lange, Petra Wolf

Proceedings of the Language and Automata Theory and Applications, 2018

2016

A Language-Theoretical Approach to Descriptive Complexity.

Michaël Cadilhac, Andreas Krebs, Klaus-Jörn Lange

Proceedings of the Developments in Language Theory - 20th International Conference, 2016

2015

Visibly Counter Languages and the Structure of NC¹.

Michael Hahn, Andreas Krebs, Klaus-Jörn Lange, Michael Ludwig

Proceedings of the Mathematical Foundations of Computer Science 2015, 2015

On Distinguishing NC¹ and NL.

Andreas Krebs, Klaus-Jörn Lange, Michael Ludwig

Proceedings of the Developments in Language Theory - 19th International Conference, 2015

2014

Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata.

Eric Allender, Klaus-Jörn Lange

Theory Comput., 2014

Visibly Counter Languages and Constant Depth Circuits.

Andreas Krebs, Klaus-Jörn Lange, Michael Ludwig

Electron. Colloquium Comput. Complex., 2014

2012

The Lower Reaches of Circuit Uniformity.

Christoph Behle, Andreas Krebs, Klaus-Jörn Lange, Pierre McKenzie

Proceedings of the Mathematical Foundations of Computer Science 2012, 2012

Dense Completeness.

Andreas Krebs, Klaus-Jörn Lange

Proceedings of the Developments in Language Theory - 16th International Conference, 2012

The Boolean Formula Value Problem as Formal Language.

Klaus-Jörn Lange

Proceedings of the Languages Alive, 2012

2011

Low uniform versions of NC1.

Christoph Behle, Andreas Krebs, Klaus-Jörn Lange, Pierre McKenzie

Electron. Colloquium Comput. Complex., 2011

2010

A Note on the P-completeness of Deterministic One-way Stack Language.

Klaus-Jörn Lange

J. Univers. Comput. Sci., 2010

2007

Characterizing TC⁰ in Terms of Infinite Groups.

Andreas Krebs, Klaus-Jörn Lange, Stephanie Reifferscheid

Theory Comput. Syst., 2007

2006

FO[<]-Uniformity.

Christoph Behle, Klaus-Jörn Lange

Proceedings of the 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 2006

2005

The dot-depth and the polynomial hierarchies correspond on the delta levels.

Bernd Borchert, Klaus-Jörn Lange, Frank Stephan, Pascal Tesson, Denis Thérien

Int. J. Found. Comput. Sci., 2005

2004

The Dot-Depth and the Polynomial Hierarchy Correspond on the Delta Levels.

Bernd Borchert, Klaus-Jörn Lange, Frank Stephan, Pascal Tesson, Denis Thérien

Proceedings of the Developments in Language Theory, 2004

Some Results on Majority Quantifiers over Words.

Klaus-Jörn Lange

Proceedings of the 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 2004

2001

On the Complexity of Some Problems on Groups Input as Multiplication Tables.

David A. Mix Barrington, Peter Kadau, Klaus-Jörn Lange, Pierre McKenzie

J. Comput. Syst. Sci., 2001

2000

Data Independence of Read, Write, and Control Structures in PRAM Computations.

Klaus-Jörn Lange, Rolf Niedermeier

J. Comput. Syst. Sci., 2000

Reversible Space Equals Deterministic Space.

Klaus-Jörn Lange, Pierre McKenzie, Alain Tapp

J. Comput. Syst. Sci., 2000

1998

RUSPACE(log <i>n</i>) $\subseteq$ DSPACE (log² <i>n</i> / log log <i>n</i>).

Eric Allender, Klaus-Jörn Lange

Theory Comput. Syst., 1998

On the Complexity of Free Monoid Morphisms.

Klaus-Jörn Lange, Pierre McKenzie

Proceedings of the Algorithms and Computation, 9th International Symposium, 1998

1997

An Unambiguous Class Possessing a Complete Set.

Klaus-Jörn Lange

Proceedings of the STACS 97, 14th Annual Symposium on Theoretical Aspects of Computer Science, Lübeck, Germany, February 27, 1997

On the Distributed Realization of Parallel Algorithms.

Klaus-Jörn Lange

Proceedings of the SOFSEM '97: Theory and Practice of Informatics, 1997

Are There Formal Languages Complete for SymSPACE(log n)?

Klaus-Jörn Lange

Proceedings of the Foundations of Computer Science: Potential - Theory, 1997

On the Complexity of Iterated Insertions.

Markus Holzer, Klaus-Jörn Lange

Proceedings of the New Trends in Formal Languages, 1997

1996

Complexity and Structure in Formal Language Theory.

Klaus-Jörn Lange

Fundam. Informaticae, 1996

StUSPACE(log n) is Contained in DSPACE((log²n)/loglog n)

Eric Allender, Klaus-Jörn Lange

Electron. Colloquium Comput. Complex., 1996

StUSPACE(log n) <= DSPACE(log²n / log log n).

Eric Allender, Klaus-Jörn Lange

Proceedings of the Algorithms and Computation, 7th International Symposium, 1996

Advocating Ownership.

Henning Fernau, Klaus-Jörn Lange, Klaus Reinhardt

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1996

Set Automata.

Klaus-Jörn Lange, Klaus Reinhardt

Proceedings of the First Conference of the Centre for Discrete Mathematics and Theoretical Computer Science, 1996

1995

The Complexity of Reconfiguring Network Models

Yosi Ben-Asher, Klaus-Jörn Lange, David Peleg, Assaf Schuster

Inf. Comput., August, 1995

1994

Empty Alternation.

Klaus-Jörn Lange, Klaus Reinhardt

Proceedings of the Mathematical Foundations of Computer Science 1994, 1994

Unambiguous Polynomial Hierarchies and Exponential Size.

Klaus-Jörn Lange, Peter Rossmanith

Proceedings of the Ninth Annual Structure in Complexity Theory Conference, Amsterdam, The Netherlands, June 28, 1994

1993

Unambiguity of Circuits.

Klaus-Jörn Lange

Theor. Comput. Sci., 1993

Data-Independences of Parallel Random Access Machines.

Klaus-Jörn Lange, Rolf Niedermeier

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1993

On the Complexities of Linear LL(1) and LR(1) Grammars.

Markus Holzer, Klaus-Jörn Lange

Proceedings of the Fundamentals of Computation Theory, 9th International Symposium, 1993

Deterministic OL Languages are of Very Low Complexity: DOL is in AC⁰.

Carsten Damm, Markus Holzer, Klaus-Jörn Lange, Peter Rossmanith

Proceedings of the Developments in Language Theory, 1993

1992

Parallel Recognition and Ranking of Context-Free Languages.

Klaus-Jörn Lange, Peter Rossmanith, Wojciech Rytter

Proceedings of the Mathematical Foundations of Computer Science 1992, 1992

The Emptiness Problem for Intersections of Regular Languages.

Klaus-Jörn Lange, Peter Rossmanith

Proceedings of the Mathematical Foundations of Computer Science 1992, 1992

Parallel Complexity of Iterated Morphisms and the Arithmetic of Small Numbers.

Carsten Damm, Markus Holzer, Klaus-Jörn Lange

Proceedings of the Mathematical Foundations of Computer Science 1992, 1992

1991

Computational Calculus and Hardest Languages of Automata with Abstract Storages.

Jürgen Dassow, Klaus-Jörn Lange

Proceedings of the Fundamentals of Computation Theory, 8th International Symposium, 1991

Unambiguity and Fewness for Logarithmic Space.

Gerhard Buntrock, Birgit Jenner, Klaus-Jörn Lange, Peter Rossmanith

Proceedings of the Fundamentals of Computation Theory, 8th International Symposium, 1991

On the Design of Parallel Programs for Machines with Distributed Memory.

Dominik Gomm, Michael Heckner, Klaus-Jörn Lange, Gerhard Riedle

Proceedings of the Distributed Memory Computing, 2nd European Conference, 1991

1990

Two results on unambiguous circuits

Klaus-Jörn Lange, Peter Rossmanith

Forschungsberichte, TU Munich, 1990

Characterizing Unambiguous Augmented Pushdown Automata by Circuits.

Klaus-Jörn Lange, Peter Rossmanith

Proceedings of the Mathematical Foundations of Computer Science 1990, 1990

1989

The Logarithmic Alternation Hierarchy Collapses: A∑₂^L = A∏₂^L.

Birgit Jenner, Bernd Kirsig, Klaus-Jörn Lange

Inf. Comput., March, 1989

1988

Decompositions of Nondeterministic Reductions.

Klaus-Jörn Lange

Theor. Comput. Sci., 1988

Complexity Theory and Formal Languages.

Klaus-Jörn Lange

Proceedings of the Machines, 1988

1987

Separation with the Ruzzo, Simon, and Tompa Relativization Implies DSPACE(log n) != NSPACE(log n).

Bernd Kirsig, Klaus-Jörn Lange

Inf. Process. Lett., 1987

A further link between formal languages and complexity theory.

Klaus-Jörn Lange, Michael Schudy

Bull. EATCS, 1987

String grammars with disconnecting or a basic root of the difficulty in graph grammar parsing.

Klaus-Jörn Lange, Emo Welzl

Discret. Appl. Math., 1987

The Logarithmic Alternation Hierarchiy Collapses: A Sigma^C_2 = A Pi^C_2.

Klaus-Jörn Lange, Birgit Jenner, Bernd Kirsig

Proceedings of the Automata, Languages and Programming, 14th International Colloquium, 1987

Dyck₁-Reductions of Context-free Languages.

Matthias Jantzen, Manfred Kudlek, Klaus-Jörn Lange, Holger Petersen

Proceedings of the Fundamentals of Computation Theory, 1987

1986

Two Characterizations of the Logarithmic Alternation Hierarchy.

Klaus-Jörn Lange

Proceedings of the Mathematical Foundations of Computer Science 1986, 1986

Decompositions of Nondeterministic Reductions (Extended Abstract).

Klaus-Jörn Lange

Proceedings of the Automata, Languages and Programming, 13th International Colloquium, 1986

1985

Recurrent Words and Simultaneous Growth in T0L Systems.

Klaus-Jörn Lange, Emo Welzl

Theor. Comput. Sci., 1985

A note on the closure of EDL-languages under erasing homomorphisms.

Klaus-Jörn Lange

Bull. EATCS, 1985

Addendum to "A note on the closure of EOL languages under erasing homomorphismus".

Klaus-Jörn Lange

Bull. EATCS, 1985

Non-Deterministic Two-Tape Automata are More Powerful Then Deterministic Ones.

Wilfried Brauer, Klaus-Jörn Lange

Proceedings of the STACS 85, 1985

String grammars with disconnecting.

Klaus-Jörn Lange, Emo Welzl

Proceedings of the Fundamentals of Computation Theory, 1985

1984

DTOL Systems and Catenativity.

Klaus-Jörn Lange

J. Inf. Process. Cybern., 1984

Nondeterministic Logspace Reductions.

Klaus-Jörn Lange

Proceedings of the Mathematical Foundations of Computer Science 1984, 1984

1983

Context-Free Controlled ETOL Systems.

Klaus-Jörn Lange

Proceedings of the Automata, 1983

1982

Kontextfrei kontrollierte ETOL-Systeme.

Klaus-Jörn Lange

PhD thesis, 1982

A Three-Restricted Normal Form Theorem for ET0L Languages.

Takashi Yokomori, Derick Wood, Klaus-Jörn Lange

Inf. Process. Lett., 1982

1980

Equivalence of Adult Languages and Extensions for DTOL Systems

Klaus-Jörn Lange

Inf. Control., November, 1980