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

This document was uploaded by one of our users. The uploader already confirmed that they had the permission to publish it. If you are author/publisher or own the copyright of this documents, please report to us by using this DMCA report form.

Simply click on the Download Book button.

Yes, Book downloads on Ebookily are 100% Free.

Sometimes the book is free on Amazon As well, so go ahead and hit "Search on Amazon"

This book constitutes the refereed proceedings of the 15th International Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS '95, held in Bangalore, India in December 1995.
The volume presents 31 full revised research papers selected from a total of 106 submissions together with full papers of four invited talks. Among the topics covered are algorithms, software technology, functional programming theory, distributed algorithms, term rewriting and constraint logic programming, complexity theory, process algebras, computational geometry, and temporal logics and verification theory.

Author(s): Mike Paterson, Shlomit Tassa, Uri Zwick (auth.), P. S. Thiagarajan (eds.)
Series: Lecture Notes in Computer Science 1026
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 1995

Language: English
Pages: 523
Tags: Computation by Abstract Devices; Algorithm Analysis and Problem Complexity; Logics and Meanings of Programs; Mathematical Logic and Formal Languages; Combinatorics; Artificial Intelligence (incl. Robotics)

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