Foundations of Software Technology and Theoretical Computer Science: 15th Conference Bangalore, India, December 18–20, 1995 Proceedings

Looking for MUM and DAD: Text-text comparisons do help....Pages 1-10
Branch and bound on the network model....Pages 11-21
A near optimal algorithm for the extended cow-path problem in the presence of relative errors....Pages 22-36
Efficient algorithms for vertex arboricity of planar graphs....Pages 37-51
A condition for the three colourability of planar locally path graphs....Pages 52-61
A framework for the specification of reactive and concurrent systems in Z....Pages 62-79
Synthesizing different development paradigms: Combining top-down with bottom-up reasoning about distributed systems....Pages 80-95
Verifying part of the ACCESS.bus protocol using PVS....Pages 96-110
Reusing batch parsers as incremental parsers....Pages 111-123
The expressive power of indeterminate primitives in asynchronous computation....Pages 124-150
The transformation calculus....Pages 151-165
Equational axiomatization of bicoercibility for polymorphic types....Pages 166-179
From causal consistency to sequential consistency in shared memory systems....Pages 180-194
Observation of software for distributed systems with RCL....Pages 195-209
Partiality and approximation schemes for local consistency in networks of constraints....Pages 210-224
Maximal extensions of simplification orderings....Pages 225-239
Average polynomial time is hard for exponential time under sn-reductions....Pages 240-247
On self-testing without the generator bottleneck....Pages 248-262
Observing behaviour categorically....Pages 263-278
An algorithm for reducing binary branchings....Pages 279-293
On the complexity of bisimilarity for value-passing processes....Pages 294-308
On the expressive power of CCS....Pages 309-323
Polarized name passing....Pages 324-337
Path balance heuristic for self-adjusting binary search trees....Pages 338-348
Pattern matching in compressed texts....Pages 349-362
All-pairs min-cut in sparse networks....Pages 363-376
Minimizing space usage in evaluation of expression trees....Pages 377-390
Smooth surfaces for multi-scale shape representation....Pages 391-412
On parallel complexity of planar triangulations....Pages 413-427
Computing a largest empty anchored cylinder, and related problems....Pages 428-442
Computing hierarchies of clusters from the euclidean minimum spanning tree in linear time....Pages 443-455
Determinizing Büchi asynchronous automata....Pages 456-470
Achilles and the tortoise climbing up the arithmetical hierarchy....Pages 471-483
Generalized temporal verification diagrams....Pages 484-498
Model checking of probabilistic and nondeterministic systems....Pages 499-513