Klaus Ambos-Spies (auth.), K. Mehlhorn (eds.)3540139125, 9783540139126
Table of contents :
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
Reviews
There are no reviews yet.