STACS 85: 2nd Annual Symposium on Theoretical Aspects of Computer Science, Saarbrücken, January 3-5, 1985 (Lecture Notes in Computer Science, 182)

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