STACS 85: 2nd Annual Symposium on Theoretical Aspects of Computer Science Saarbrücken, January 3–5, 1985

On the relative complexity of subproblems of intractable problems....Pages 1-12
On Lovász' lattice reduction and the nearest lattice point problem....Pages 13-20
Layouts with wires of balanced length....Pages 21-31
On the single-operation worst-case time complexity of the disjoint set union problem....Pages 32-38
Deterministic languages and non-generators....Pages 39-46
Simulation of large networks on smaller networks....Pages 47-58
Petri nets and algebraic calculi of processes....Pages 59-70
Non-deterministic two-tape automata are more powerful than deterministic ones....Pages 71-79
Construction of a family of factorizing codes....Pages 80-86
On hotz groups and homomorphic images of sentential form languages....Pages 87-97
Using domain algebras to prove the correctness of a compiler....Pages 98-108
Sorting and recognition problems for ordered sets....Pages 109-118
Tree automata and logic programs....Pages 119-130
Structure of relations satisfying certain families of dependencies....Pages 131-142
A single source shortest path algorithm for a planar distributed network....Pages 143-150
An algorithm for two-layer channel routing....Pages 151-160
New algorithms for special cases of the hidden line elimination problem....Pages 161-172
An algorithm to construct Minkowski-reduced lattice-bases....Pages 173-179
Base Non Finie de Varietes....Pages 180-186
Proximity on a grid....Pages 187-196
An O(N 1.5+ε ) expected time algorithm for canonization and isomorphism testing of trivalent graphs....Pages 197-207
On the complexity of deadlock recovery....Pages 208-218
On the planar monotone computation of threshold functions....Pages 219-230
Planar circuits have short specifications....Pages 231-242
Shortest paths on polyhedral surfaces....Pages 243-254
Fairness in context Free grammars under canonical derivations....Pages 255-266
Distributed termination in CSP symmetric solutions with minimal storage....Pages 267-278
A dynamization of the All Pairs Least Cost Path Problem....Pages 279-286
Boundedness, empty channel detection and synchronization for communicating finite state machines....Pages 287-298
Deriving stack semantics congruent to standard denotational semantics....Pages 299-309
Translating polygons in the plane....Pages 310-321
Geometric containment is not reducible to Pareto dominance....Pages 322-327
The volume of the union of many spheres and point inclusion problems....Pages 328-338
Combined simplicity and immunity in relativized NP....Pages 339-350
Groups, codes and unambiguous automata....Pages 351-362
Reduced memory space for multi-dimensional search trees (extended abstract)....Pages 363-374