ISTCS '92, the Israel Symposium on the Theory of Computing and Systems, cameabout spontaneously as a result of informal interaction between a group of people who viewed the conference as an appropriate expression of Israeli strength in theoretical aspects of computing and systems. The enthusiasm that the symposium created resulted in the submission of a large number of extremely high quality papers, which led in turn to strict acceptance criteria. This volume contains nineteen selected papers representing the cream of Israeli talent in the field, on a variety of active and interesting topics in the theory of computing and systems.
Author(s): Jingsen Chen (auth.), D. Dolev, Z. Galil, M. Rodeh (eds.)
Series: Lecture Notes in Computer Science 601
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 1992
Language: English
Pages: 224
Tags: Computation by Abstract Devices; Algorithm Analysis and Problem Complexity; Logics and Meanings of Programs; Mathematical Logic and Formal Languages; Memory Structures; Computer Communication Networks
Merging and splitting priority queues and deques in parallel....Pages 1-11
Lower bounds for the complexity of functions in a realistic RAM model....Pages 12-23
On Boolean decision trees with faulty nodes....Pages 24-31
Interval graphs, interval orders and the consistency of temporal events (extended abstract)....Pages 32-42
Higher order functions in first order logics....Pages 43-54
Reduction relations in strict applicative languages....Pages 55-66
Approximation algorithms for minimum time broadcast....Pages 67-78
The complexity of reconfiguring network models....Pages 79-90
Optimal mapping in direct mapped cache environments....Pages 91-102
New algorithms for generalized network flows....Pages 103-114
Factoring polynomials via relation-finding....Pages 115-121
New resultant inequalities and complex polynomial factorization....Pages 122-136
Can symmetric Toeplitz solvers be strongly stable?....Pages 137-146
Bounds on parallel computation of multivariate polynomials....Pages 147-153
Time-lapse snapshots....Pages 154-170
Concurrent Timestamping made simple....Pages 171-183
Distributed evaluation: a tool for constructing distributed detection programs....Pages 184-194
Foundations of asymptotical theory of Determinate Compact Testing....Pages 195-206
Optimal k-colouring and k-nesting of intervals....Pages 207-220
