Clemens Lautemann

Arnaud Durand, Clemens Lautemann, Malika More: A simple proof of the polylog counting ability of first-order logic: guest column. SIGACT News 38(4): 40-45 (2007)

Michal Koucký, Clemens Lautemann, Sebastian Poloczek, Denis Thérien: Circuit Lower Bounds via Ehrenfeucht-Fraisse Games. IEEE Conference on Computational Complexity 2006: 190-201

Clemens Lautemann, Pascal Tesson, Denis Thérien: An Algebraic Point of View on the Crane Beach Property. CSL 2006: 426-440

Arnaud Durand, Clemens Lautemann, Malika More: Counting Results in Weak Formalisms. Circuits, Logic, and Games 2006

David A. Mix Barrington, Neil Immerman, Clemens Lautemann, Nicole Schweikardt, Denis Thérien: First-order expressibility of languages with neutral letters or: The Crane Beach conjecture. J. Comput. Syst. Sci. 70(2): 101-127 (2005)

Clemens Lautemann, Pierre McKenzie, Thomas Schwentick, Heribert Vollmer: The Descriptive Complexity Approach to LOGCFL. J. Comput. Syst. Sci. 62(4): 629-652 (2001)

David A. Mix Barrington, Neil Immerman, Clemens Lautemann, Nicole Schweikardt, Denis Thérien: The Crane Beach Conjecture. LICS 2001: 187-196

Clemens Lautemann, Nicole Schweikardt: An Ehrenfeucht-Fraïssé Approach to Collapse Results for First-Order Queries over Embedded Databases. STACS 2001: 455-466

Clemens Lautemann, Bernhard Weinzinger: MonadicNLIN and Quantifier-Free Reductions. CSL 1999: 322-337

Clemens Lautemann, Nicole Schweikardt, Thomas Schwentick: A Logical Characterisation of Linear Time on Nondeterministic Turing Machines. STACS 1999: 143-152

Clemens Lautemann, Pierre McKenzie, Thomas Schwentick, Heribert Vollmer: The Descriptive Complexity Approach to LOGCFL. STACS 1999: 444-454

Clemens Lautemann, Thomas Schwentick, Iain A. Stewart: Positive Versions of Polynomial Time. Inf. Comput. 147(2): 145-170 (1998)

Arnaud Durand, Clemens Lautemann, Thomas Schwentick: Subclasses of Binary NP. J. Log. Comput. 8(2): 189-207 (1998)

Clemens Lautemann, Pierre McKenzie, Thomas Schwentick, Heribert Vollmer: The descriptive complexity approach to LOGCFL. CoRR cs.CC/9809114 (1998)

Clemens Lautemann, Pierre McKenzie, Thomas Schwentick, Heribert Vollmer: The Descriptive Complexity Approach to LOGCFL. Electronic Colloquium on Computational Complexity (ECCC) 5(59) (1998)

Clemens Lautemann, Thomas Schwentick, Iain A. Stewart: On Positive P. IEEE Conference on Computational Complexity 1996: 162-170

Clemens Lautemann, Thomas Schwentick, Denis Thérien: Logics For Context-Free Languages. CSL 1994: 205-216

Annegret Habel, Hans-Jörg Kreowski, Clemens Lautemann: A Comparison of Compatible, Finite, and Inductive Graph Properties. Theor. Comput. Sci. 110(1): 145-168 (1993)

Ulrich Hertrampf, Clemens Lautemann, Thomas Schwentick, Heribert Vollmer, Klaus W. Wagner: On the Power of Polynomial Time Bit-Reductions (Extended Abstract). Structure in Complexity Theory Conference 1993: 200-207

Clemens Lautemann: Logical Definability of NP-Optimization Problems with Monadic Auxiliary Predicates. CSL 1992: 327-339

Ulrich Hertrampf, Clemens Lautemann, Thomas Schwentick, Heribert Vollmer, Klaus W. Wagner: On the Power of Polynomial Bit-Reductions. Universität Trier, Mathematik/Informatik, Forschungsbericht 92-28 (1992)

Frank Drewes, Clemens Lautemann: Incremental Termination Proofs and the Length of Derivations. RTA 1991: 49-61

Clemens Lautemann: Tree Automata, Tree Decomposition and Hyperedge Replacement. Graph-Grammars and Their Application to Computer Science 1990: 520-537

Clemens Lautemann: The Complexity of Graph Languages Generated by Hyperedge Replacement. Acta Inf. 27(5): 399-421 (1989)

Dieter Hofbauer, Clemens Lautemann: Termination Proofs and the Length of Derivations (Preliminary Version). RTA 1989: 167-177

Clemens Lautemann: A note on polynomial interpretation. Bulletin of the EATCS 36: 129-130 (1988)

Clemens Lautemann: Decomposition Trees: Structured Graph Representation and Efficient Algorithms. CAAP 1988: 28-39

Clemens Lautemann: Efficient Algorithms on Context-Free Graph Grammars. ICALP 1988: 362-378

Clemens Lautemann, Friedhelm Meyer auf der Heide: Lower Time Bounds for Integer Programming with Two Variables. Inf. Process. Lett. 21(2): 101-105 (1985)

Clemens Lautemann: BPP and the Polynomial Hierarchy. Inf. Process. Lett. 17(4): 215-217 (1983)