## Foundations of Software Technology and Theoretical Computer Science: 14th Conference, Madras, India, December 15 - 17, 1994. ProceedingsThis 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 |

### Common terms and phrases

Abstract actions algorithm application approximation associated assume block bound branching buffers called circuit clauses coloring complexity component Computer Computer Science condition consider consists constant constructed contains convex corresponding defined definition denote depth described eave edge elements equation equivalence example exists expression extended finite function give given graph Hence holds induction infinite input instance integer introduce labelled language least Lemma length linear logic marked matching merge method node Note notion Observe obtained occurs operations optimal output parallel path performance polynomial positive possible probability problem procedure Proceedings proof prove random reduced relation represented respectively result root rule satisfies scheme semantics sequence solution step structure substitutions tape technique Theorem theory tree unification variables vertex vertices visible weight