STACS 90: 7th Annual Symposium on Theoretical Aspects of Computer Science Rouen, France, February 22–24, 1990 Proceedings

Eric Allender, Richard Beigel, Ulrich Hertrampf, Steven Homer (auth.), Christian Choffrut, Thomas Lengauer (eds.)3540522824, 9783540522829

The Symposium on Theoretical Aspects of Computer Science is organized jointly by the Special Interest Group for Applied Mathematics of AFCET (Association Française de Cybernétique Economique et Technique) and the Special Interest Group for Theoretical Computer Sciences of GI (Gesellschaft für Informatik). It is held alternately in France and in Germany. This volume contains two invited papers, on combinatorial methods in computer science, and on the complexity of local optimization, and 24 contributions on theoretical aspects of computer science. Some software systems are presented showing the possibilities of applying theoretical research to the realization of software tools.

---

Table of contents :
A note on the almost-everywhere hierarchy for nondeterministic time….Pages 1-11
The ring of k -regular sequences….Pages 12-23
Minimal pairs and complete problems….Pages 24-36
Hiding instances in multioracle queries….Pages 37-48
Counting classes: Thresholds, parity, mods, and fewness….Pages 49-57
Playing games of incomplete information….Pages 58-69
Caterpillars and context-free languages….Pages 70-81
Semi-commutations and algebraic languages….Pages 82-94
Towards a process semantics in the logic programming style….Pages 95-108
Parallel computations on strings and arrays….Pages 109-125
Minimum vertex hulls for polyhedral domains….Pages 126-137
Combinatorial rewriting on traces….Pages 138-151
Kolmogorov complexity, restricted nondeterminism and generalized spectra….Pages 152-164
Relation-sorted algebraic specifications with built-in coercers: Basic notions and results….Pages 165-175
Computational power of one-way multihead finite automata….Pages 176-187
Updating almost complete trees or one level makes all the difference….Pages 188-194
Sorting the sums (x i +y j ) in O(n 2 ) comparisons….Pages 195-206
Efficient checking of computations….Pages 207-215
Hard promise problems and nonuniform complexity….Pages 216-226
On the construction of abstract voronoi diagrams….Pages 227-239
Approximation of convex figures by pairs of rectangles….Pages 240-249
Nonblocking graphs: Greedy algorithms to compute disjoint paths….Pages 250-262
Infinite trees and automaton definable relations over ω-words….Pages 263-277
Enumerative Combinatorics and Computer Science….Pages 278-284
Failures semantics based on interval semiwords is a congruence for refinement….Pages 285-297
The analysis of local search problems and their heuristics….Pages 298-311