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.
Author(s): Dexter Kozen (auth.), P. S. Thiagarajan (eds.)
Series: Lecture Notes in Computer Science 880
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 1994
Language: English
Commentary: (add ocr)
Pages: 460
Tags: Algorithm Analysis and Problem Complexity; Logics and Meanings of Programs; Combinatorics; Computer Graphics; Computation by Abstract Devices; Mathematical Logic and Formal Languages
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
