For more than a decade, Foundations of Software Technology and Theoretical Computer Science Conferences have been providing an annual forum for the presentation of new research results in India and abroad. This year, 119 papers from 20 countries were submitted. Each paper was reviewed by at least three reviewers, and 33 papers were selected for presentation and included in this volume, grouped into parts on type theory, parallel algorithms, term rewriting, logic and constraint logic programming, computational geometry and complexity, software technology, concurrency, distributed algorithms, and algorithms and learning theory. Also included in the volume are the five invited papers presented at theconference.
Author(s): Juris Hartmanis (auth.), Rudrapatna K. Shyamasundar (eds.)
Series: Lecture Notes in Computer Science 761
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 1993
Language: English
Pages: 462
Tags: Logics and Meanings of Programs; Computation by Abstract Devices; Programming Languages, Compilers, Interpreters; Mathematical Logic and Formal Languages; Combinatorics; Computer Graphics
Some observations about the nature of computer science....Pages 1-12
Essential intersection type assignment....Pages 13-23
Label-selective λ-calculus syntax and confluence....Pages 24-40
Conventional and uniqueness typing in graph rewrite systems....Pages 41-51
A meta-language for typed object-oriented languages....Pages 52-71
Preemption in concurrent systems....Pages 72-93
Local versus non-local computation of length of digitized curves....Pages 94-103
Data-independences of parallel random access machines....Pages 104-113
Proving termination of logic programs by transforming them into equivalent term rewriting systems....Pages 114-124
Completeness of hierarchical combinations of term rewriting systems....Pages 125-138
Higher-order and semantic unification....Pages 139-150
A conservative extension of first-order logic and its applications to theorem proving....Pages 151-160
Well-founded Ordered Search (extended abstract)....Pages 161-171
A real-time interval logic and its decision procedure....Pages 173-192
On the semantics of optimization predicates in CLP languages....Pages 193-204
Incremental algorithms for constraint solving and entailment over rational trees....Pages 205-217
Proximity problems and the Voronoi diagram on a rectilinear plane with rectangular obstacles....Pages 218-227
Feasibility of design in stereolithography....Pages 228-237
Compact location problems....Pages 238-247
On some communication complexity problems related to threshold functions....Pages 248-259
Recursiveness over the complex numbers is time-bounded....Pages 260-267
A lower bound for solvability of polynomial equations....Pages 268-283
Reuse of proofs in software verification....Pages 284-293
Induce-statements and induce-expressions: Constructs for inductive programming....Pages 294-305
A graphic language based on timing diagrams....Pages 306-316
Software technology: Integrating theory and practice....Pages 317-317
Generating degrees of belief from statistical information: An overview....Pages 318-325
Complexity results for 1-safe nets....Pages 326-337
Some results about logical descriptions of non deterministic behaviours....Pages 338-347
Order structures and generalisations of Szpilrajn's theorem....Pages 348-357
ICSP and its relationship with ACSP and CSP....Pages 358-372
On reduction-based process semantics....Pages 373-387
Keeping track of the latest gossip: Bounded time-stamps suffice....Pages 388-399
Time optimal self-stabilizing spanning tree algorithms....Pages 400-410
Efficient algorithm to sort linear combinations of arrays....Pages 411-418
A simple file structure for the weighted dictionary problem....Pages 419-435
Searching, sorting and randomised algorithms for Central Elements and ideal counting in posets....Pages 436-443
Learning classes of Regular and Linear Languages in Valiant's learnability framework....Pages 444-453
