STACS 90

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.