This book constitutes the refereed proceedings of the 16th International Conference on Foundations of Software Technology and Theoretical Computer Science, FST&TCS '96, held in Hyderabad, India, in December 1996.
The volume presents 28 revised full papers selected from a total of 98 submissions; also included are four invited contributions. The papers are organized in topical sections on computational geometry, process algebras, program semantics, algorithms, rewriting and equational-temporal logics, complexity theory, and type theory.
Author(s): Eric Allender (auth.), V. Chandru, V. Vinay (eds.)
Series: Lecture Notes in Computer Science 1180
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 1996
Language: English
Pages: 395
Tags: Logics and Meanings of Programs; Algorithm Analysis and Problem Complexity; Mathematical Logic and Formal Languages; Computer Graphics
Circuit complexity before the dawn of the new millennium....Pages 1-18
A lambda calculus with letrecs and barriers....Pages 19-36
Tables....Pages 37-42
Mechanized formal methods: Progress and prospects....Pages 43-51
The parameter space of the d -step conjecture....Pages 52-63
On the complexity of approximating Euclidean traveling salesman tours and minimum spanning trees....Pages 64-75
Efficient computation of rectilinear geodesic voronoi neighbor in presence of obstacles....Pages 76-87
Weak bisimulation and model checking for Basic Parallel Processes....Pages 88-99
Testing processes for efficiency....Pages 100-110
Regularity is decidable for normed PA processes in polynomial time....Pages 111-122
Dynamic maintenance of shortest path trees in simple polygons....Pages 123-134
Close approximations of minimum rectangular coverings....Pages 135-146
A new competitive algorithm for agent searching in unknown streets....Pages 147-155
On the design of hybrid control systems using automata models....Pages 156-167
Constraint retraction in FD....Pages 168-179
Winskel is (almost) right....Pages 180-192
An optimal deterministic algorithm for online b-matching....Pages 193-199
Tight bounds for prefetching and buffer management algorithms for parallel I/O systems....Pages 200-211
Complexity of the gravitational method for linear programming....Pages 212-223
Optimal and information theoretic syntactic Pattern Recognition involving traditional and transposition errors....Pages 224-237
Minimal relative normalization in orthogonal expression reduction systems....Pages 238-249
Trace consistency and inevitability....Pages 250-261
Finite state implementations of knowledge-based programs....Pages 262-273
Higher-order proof by consistency....Pages 274-285
Advocating ownership....Pages 286-297
Non-cancellative Boolean circuits: A generalization of monotone Boolean circuits....Pages 298-309
Limitations of the QRQW and EREW PRAM models....Pages 310-321
Pinpointing computation with modular queries in the Boolean hierarchy....Pages 322-334
Characterization of the principal type of normal forms in an intersection type system....Pages 335-346
Correcting type errors in the Curry System....Pages 347-358
Immediate fixpoints and their use in groundness analysis....Pages 359-370
Graph types for monadic mobile processes....Pages 371-386
