Foundation of Software Technology and Theoretical Computer Science: 14th Conference Madras, India, December 15–17, 1994 Proceedings

Efficient resolution of singularities of plane curves....Pages 1-11
On the interactive complexity of graph reliability....Pages 12-23
Matching upper and lower bounds for simulations of several tapes on one multidimensional tape....Pages 24-35
The complexity of computing over quasigroups....Pages 36-47
Non-commutative computation, depth reduction, and skew circuits (extended abstract)....Pages 48-59
Inductive definitions and type theory an introduction (preliminary version)....Pages 60-76
Interpreter verification for a functional language....Pages 77-88
An epistemic foundation for logic programming with uncertainty....Pages 89-100
On typed calculi with a merge operator....Pages 101-112
Incremental algorithms for the single-source shortest path problem....Pages 113-124
An O(n) algorithm for realizing degree sequences....Pages 125-136
Coloring semi-random graphs in polynomial expected time....Pages 137-148
Finite-state strategies in regular infinite games....Pages 149-158
Location of the largest empty rectangle among arbitrary obstacles....Pages 159-170
Efficient parallel and linear time sequential split decomposition (extended abstract)....Pages 171-180
Algorithms for convex visibility problems....Pages 181-192
Lower bounds for parallel algebraic decision trees, complexity of convex hulls and related problems....Pages 193-204
Localities and failures (extended summary)....Pages 205-216
Priority and abstraction in process algebra....Pages 217-230
On the computational power of operators in ICSP with fairness....Pages 231-242
Decidability of timed language-inclusion for networks of real-time communicating sequential processes....Pages 243-255
My favorite ten complexity theorems of the past decade....Pages 256-275
Solving a unification problem under constrained substitutions using tree automata....Pages 276-287
Automata-driven efficient subterm unification....Pages 288-299
Randomized approximation algorithms in combinatorial optimization....Pages 300-317
A limited-backtrack greedy schema for approximation algorithms....Pages 318-329
On approximation scheme preserving reductibility and its applications....Pages 330-341
Approximation schemes using L-reductions....Pages 342-353
An explanation of splaying....Pages 354-365
Proving non-reachability by modulo-place-invariants....Pages 366-377
Soundness and completeness of UNITY logic....Pages 378-389
Efficient algorithms for the transformation between different types of binary decision diagrams....Pages 390-401
Extending the limits of sequentially phased reasoning....Pages 402-413
Foundations for faster external sorting....Pages 414-425
Branching rules for satisfiability....Pages 426-437
Using linear arithmetic procedure for generating induction schemes....Pages 438-449