Foundations of Software Technology and Theoretical Computer Science: 14th Conference, Madras, India, December 15 - 17, 1994. Proceedings

Front Cover
P.S. Thiagarajan
Springer Science & Business Media, Nov 23, 1994 - Computers - 460 pages
This volume presents the proceedings of the 14th International Conference on the Foundations of Software Technology and Theoretical Computer Science, FST&TCS-14, held in Madras, India in December 1994.
Besides the five invited papers by well-known researchers, it includes 31 full refereed research papers selected out of a total of 140 submissions. The papers contribute to the whole area of theoretical computer science with an emphasis on algorithms and complexity. Other topics covered are program semantics, program verification, formal logic, computational geometry, concurrency, unification, and discrete mathematics.
 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

Efficient Resolution of Singularities of Plane Curves
1
On the Interactive Complexity of Graph Reliability
12
Matching Upper and Lower Bounds for Simulations of Several Tapes on One Multidimensional Tape
24
The Complexity of Computing over Quasigroups
36
Noncommutative Computation Depth Reduction and Skew Circuits
48
Inductive Definitions and Type Theory an Introduction Preliminary version
60
Interpreter Verification for a Functional Language
77
An Epistemic Foundation for Logic Programming with Uncertainty
89
On the Computational Power of Operators in ICSP with Fairness
231
Decidability of Timed LanguageInclusion for Networks of RealTime Communicating Sequential Processes
243
My Favorite Ten Complexity Theorems of the Past Decade
256
Solving a Unification Problem under Constrained Substitutions Using Tree Automata
276
AutomataDriven Efficient Subterm Unification
288
Randomized Approximation Algorithms in Combinatorial Optimization
300
A LimitedBacktrack Greedy Schema for Approximation Algorithms
318
Reducibility and Its Applications
330

On Typed Calculi with a Merge Operator
101
Incremental algorithms for the singlesource shortest path problem
113
An On Algorithm for Realizing Degree Sequences
125
Coloring SemiRandom Graphs in Polynomial Expected Time
137
FiniteState Strategies in Regular Infinite Games
149
Location of the Largest Empty Rectangle among Arbitrary Obstacles
159
Efficient Parallel and Linear Time Sequential Split Decomposition
171
Algorithms for Convex Visibility Problems
181
Lower Bounds for Parallel Algebraic Decision Trees Complexity of Convex Hulls and Related Problems
193
Localities and Failures
205
Priority and Abstraction in Process Algebra
217
Approximation Schemes Using LReductions
342
An Explanation of Splaying
354
Proving NonReachability by ModuloPlaceInvariants
366
Soundness and Completeness of UNITY Logic
378
Efficient Algorithms for the Transformation between Different Types of Binary Decision Diagrams
390
Extending the Limits of Sequentially Phased Reasoning
402
Foundations for Faster External Sorting
414
Branching Rules for Satisfiability
426
Using Linear Arithmetic Procedure for Generating Induction Schemes
438
Copyright

Common terms and phrases

Bibliographic information