Clemens Lautemann

According to our database, Clemens Lautemann authored at least 29 papers between 1983 and 2007.

Collaborative distances:

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

2007

A simple proof of the polylog counting ability of first-order logic: guest column.

Arnaud Durand, Clemens Lautemann, Malika More

SIGACT News, 2007

2006

Counting Results in Weak Formalisms.

Arnaud Durand, Clemens Lautemann, Malika More

Proceedings of the Circuits, Logic, and Games, 08.11. - 10.11.2006, 2006

An Algebraic Point of View on the Crane Beach Property.

Clemens Lautemann, Pascal Tesson, Denis Thérien

Proceedings of the Computer Science Logic, 20th International Workshop, 2006

Circuit Lower Bounds via Ehrenfeucht-Fraisse Games.

Michal Koucký, Clemens Lautemann, Sebastian Poloczek, Denis Thérien

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

2005

First-order expressibility of languages with neutral letters or: The Crane Beach conjecture.

David A. Mix Barrington, Neil Immerman, Clemens Lautemann, Nicole Schweikardt, Denis Thérien

J. Comput. Syst. Sci., 2005

2001

The Descriptive Complexity Approach to LOGCFL.

Clemens Lautemann, Pierre McKenzie, Thomas Schwentick, Heribert Vollmer

J. Comput. Syst. Sci., 2001

An Ehrenfeucht-Fraïssé Approach to Collapse Results for First-Order Queries over Embedded Databases.

Clemens Lautemann, Nicole Schweikardt

Proceedings of the STACS 2001, 2001

The Crane Beach Conjecture.

David A. Mix Barrington, Neil Immerman, Clemens Lautemann, Nicole Schweikardt, Denis Thérien

Proceedings of the 16th Annual IEEE Symposium on Logic in Computer Science, 2001

1999

A Logical Characterisation of Linear Time on Nondeterministic Turing Machines.

Clemens Lautemann, Nicole Schweikardt, Thomas Schwentick

Proceedings of the STACS 99, 1999

MonadicNLIN and Quantifier-Free Reductions.

Clemens Lautemann, Bernhard Weinzinger

Proceedings of the Computer Science Logic, 13th International Workshop, 1999

1998

Subclasses of Binary NP.

Arnaud Durand, Clemens Lautemann, Thomas Schwentick

J. Log. Comput., 1998

Positive Versions of Polynomial Time.

Clemens Lautemann, Thomas Schwentick, Iain A. Stewart

Inf. Comput., 1998

1996

On Positive P.

Clemens Lautemann, Thomas Schwentick, Iain A. Stewart

Proceedings of the Eleveth Annual IEEE Conference on Computational Complexity, 1996

1994

Logics For Context-Free Languages.

Clemens Lautemann, Thomas Schwentick, Denis Thérien

Proceedings of the Computer Science Logic, 8th International Workshop, 1994

1993

A Comparison of Compatible, Finite, and Inductive Graph Properties.

Annegret Habel, Hans-Jörg Kreowski, Clemens Lautemann

Theor. Comput. Sci., 1993

On the Power of Polynomial Time Bit-Reductions (Extended Abstract).

Ulrich Hertrampf, Clemens Lautemann, Thomas Schwentick, Heribert Vollmer, Klaus W. Wagner

Proceedings of the Eigth Annual Structure in Complexity Theory Conference, 1993

1992

On the Power of Polynomial Bit-Reductions

Ulrich Hertrampf, Clemens Lautemann, Thomas Schwentick, Heribert Vollmer, Klaus W. Wagner

Universität Trier, Mathematik/Informatik, Forschungsbericht, 1992

Logical Definability of NP-Optimization Problems with Monadic Auxiliary Predicates.

Clemens Lautemann

Proceedings of the Computer Science Logic, 6th Workshop, 1992

1991

Some modifications of auxiliary pushdown automata.

Gerhard Buntrock, Frank Drewes, Clemens Lautemann, Till Mossakowski

RAIRO Theor. Informatics Appl., 1991

Incremental Termination Proofs and the Length of Derivations.

Frank Drewes, Clemens Lautemann

Proceedings of the Rewriting Techniques and Applications, 4th International Conference, 1991

1990

The Complexity of Graph Languages Generated by Hyperedge Replacement.

Clemens Lautemann

Acta Informatica, 1990

Tree Automata, Tree Decomposition and Hyperedge Replacement.

Clemens Lautemann

Proceedings of the Graph-Grammars and Their Application to Computer Science, 1990

1989

Termination Proofs and the Length of Derivations (Preliminary Version).

Dieter Hofbauer, Clemens Lautemann

Proceedings of the Rewriting Techniques and Applications, 3rd International Conference, 1989

1988

A note on polynomial interpretation.

Clemens Lautemann

Bull. EATCS, 1988

Efficient Algorithms on Context-Free Graph Grammars.

Clemens Lautemann

Proceedings of the Automata, Languages and Programming, 15th International Colloquium, 1988

Decomposition Trees: Structured Graph Representation and Efficient Algorithms.

Clemens Lautemann

Proceedings of the CAAP '88, 1988

1985

Lower Time Bounds for Integer Programming with Two Variables.

Clemens Lautemann, Friedhelm Meyer auf der Heide

Inf. Process. Lett., 1985

1983

Polynomielle probabilistische Komplexitätsklassen.

Clemens Lautemann

PhD thesis, 1983

BPP and the Polynomial Hierarchy.

Clemens Lautemann

Inf. Process. Lett., 1983