Clemens Lautemann

According to our database1, Clemens Lautemann
  • authored at least 32 papers between 1983 and 2007.
  • has a "Dijkstra number"2 of four.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

On csauthors.net:

Bibliography

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

2006
Counting Results in Weak Formalisms.
Proceedings of the Circuits, Logic, and Games, 08.11. - 10.11.2006, 2006

An Algebraic Point of View on the Crane Beach Property.
Proceedings of the Computer Science Logic, 20th International Workshop, 2006

Circuit Lower Bounds via Ehrenfeucht-Fraisse Games.
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.
J. Comput. Syst. Sci., 2005

2001
The Descriptive Complexity Approach to LOGCFL.
J. Comput. Syst. Sci., 2001

An Ehrenfeucht-Fraïssé Approach to Collapse Results for First-Order Queries over Embedded Databases.
Proceedings of the STACS 2001, 2001

The Crane Beach Conjecture.
Proceedings of the 16th Annual IEEE Symposium on Logic in Computer Science, 2001

1999
A Logical Characterisation of Linear Time on Nondeterministic Turing Machines.
Proceedings of the STACS 99, 1999

The Descriptive Complexity Approach to LOGCFL.
Proceedings of the STACS 99, 1999

MonadicNLIN and Quantifier-Free Reductions.
Proceedings of the Computer Science Logic, 13th International Workshop, 1999

1998
Subclasses of Binary NP.
J. Log. Comput., 1998

Positive Versions of Polynomial Time.
Inf. Comput., 1998

The Descriptive Complexity Approach to LOGCFL
Electronic Colloquium on Computational Complexity (ECCC), 1998

The descriptive complexity approach to LOGCFL
CoRR, 1998

1996
On Positive P.
Proceedings of the Eleveth Annual IEEE Conference on Computational Complexity, 1996

1994
Logics For Context-Free Languages.
Proceedings of the Computer Science Logic, 8th International Workshop, 1994

1993
A Comparison of Compatible, Finite, and Inductive Graph Properties.
Theor. Comput. Sci., 1993

On the Power of Polynomial Time Bit-Reductions (Extended Abstract).
Proceedings of the Eigth Annual Structure in Complexity Theory Conference, 1993

1992
On the Power of Polynomial Bit-Reductions
Universität Trier, Mathematik/Informatik, Forschungsbericht, 1992

Logical Definability of NP-Optimization Problems with Monadic Auxiliary Predicates.
Proceedings of the Computer Science Logic, 6th Workshop, 1992

1991
Some modifications of auxiliary pushdown automata.
ITA, 1991

Incremental Termination Proofs and the Length of Derivations.
Proceedings of the Rewriting Techniques and Applications, 4th International Conference, 1991

1990
The Complexity of Graph Languages Generated by Hyperedge Replacement.
Acta Inf., 1990

Tree Automata, Tree Decomposition and Hyperedge Replacement.
Proceedings of the Graph-Grammars and Their Application to Computer Science, 1990

1989
Termination Proofs and the Length of Derivations (Preliminary Version).
Proceedings of the Rewriting Techniques and Applications, 3rd International Conference, 1989

1988
A note on polynomial interpretation.
Bulletin of the EATCS, 1988

Efficient Algorithms on Context-Free Graph Grammars.
Proceedings of the Automata, Languages and Programming, 15th International Colloquium, 1988

Decomposition Trees: Structured Graph Representation and Efficient Algorithms.
Proceedings of the CAAP '88, 1988

1985
Lower Time Bounds for Integer Programming with Two Variables.
Inf. Process. Lett., 1985

1983
Polynomielle probabilistische Komplexitätsklassen.
PhD thesis, 1983

BPP and the Polynomial Hierarchy.
Inf. Process. Lett., 1983


  Loading...