STACS 90

Thomas Lengauer, born 1952, studied Mathematics and Informatics at Berlin and Stanford. After a brief stay at the Bell Laboratories, he held various academic positions at the universities of Saarbruecken, Paderborn, and Bonn. From 1992 to 2001, he headed the Institue for Algorithms and Scientific Computing at the GBM in Sankt Augustin (Germany). Since 2001, he is director at the Max-Planck-Institute for Informatics in Saarbruecken (Germany).Professor Lengauer has recently been awarded the Konrad-Zuse-Medal, the highest honor of the German Informatics Society.

A note on the almost-everywhere hierarchy for nondeterministic time.- The ring of k-regular sequences.- Minimal pairs and complete problems.- Hiding instances in multioracle queries.- Counting classes: Thresholds, parity, mods, and fewness.- Playing games of incomplete information.- Caterpillars and context-free languages.- Semi-commutations and algebraic languages.- Towards a process semantics in the logic programming style.- Parallel computations on strings and arrays.- Minimum vertex hulls for polyhedral domains.- Combinatorial rewriting on traces.- Kolmogorov complexity, restricted nondeterminism and generalized spectra.- Relation-sorted algebraic specifications with built-in coercers: Basic notions and results.- Computational power of one-way multihead finite automata.- Updating almost complete trees or one level makes all the difference.- Sorting the sums (xi+yj) in O(n2) comparisons.- Efficient checking of computations.- Hard promise problems and nonuniform complexity.- On the construction of abstract voronoi diagrams.- Approximation of convex figures by pairs of rectangles.- Nonblocking graphs: Greedy algorithms to compute disjoint paths.- Infinite trees and automaton definable relations over ?-words.- Enumerative Combinatorics and Computer Science.- Failures semantics based on interval semiwords is a congruence for refinement.- The analysis of local search problems and their heuristics.