14. FSTTCS 1994: Madras, India

Invited Talk

• Dexter Kozen:
  Efficient Resolution of Singularities of Plane Curves. 1-11
  

Complexity Theory

• Jean Marc Couveignes, Juan Francisco Diaz-Frias, Michel de Rougemont, Miklos Santha:
  On the Interactive Complexity of Graph Reliability. 12-23
  
• Martin Dietzfelbinger, Martin Hühne:
  Matching Upper and Lower Bounds for Simulation of Several Tapes on One Multidimensional Tape. 24-35
  
• Hervé Caussinus, François Lemieux:
  The Complexity of Computing over Quasigroups. 36-47
  
• Meena Mahajan, V. Vinay:
  Non-commutative Computation, Depth Reduction, and Skew Circuits (Extended Abstract). 48-59
  

Invited Talk

• Thierry Coquand, Peter Dybjer:
  Inductive Definitions and Type Theory: an Introduction (Preliminary Version). 60-76
  
• Manfred Broy, Ursula Hinkel, Tobias Nipkow, Christian Prehofer, Birgit Schieder:
  Interpreter Verification for a Functional Language. 77-88
  
• Laks V. S. Lakshmanan:
  An Epistemic Foundation for Logic Programming with Uncertainty. 89-100
  
• Hideki Tsuiki:
  On Typed Calculi with a Merge Operator. 101-112
  

Algorithms

• Daniele Frigioni, Alberto Marchetti-Spaccamela, Umberto Nanni:
  Incremental Algorithms for the Single-Source Shortest Path Problem. 113-124
  
• Srinivasa Rao Arikati, Anil Maheshwari:
  An O(n) Algorithm for Realizing Degree Sequences. 125-136
  
• C. R. Subramanian, C. E. Veni Madhavan:
  Coloring Semi-Random Graphs in Polynomial Expected Time. 137-148
  

Invited Talk

• Wolfgang Thomas:
  Finite-State Strategies in Regular Infinite Games. 149-158
  

Algorithms

• Subhas C. Nandy, Arani Sinha, Bhargab B. Bhattacharya:
  Location of the Largest Empty Rectangle among Arbitrary Obstacles. 159-170
  
• Elias Dahlhaus:
  Efficient Parallel and Linear Time Sequential Split Decomposition (Extended Abstract). 171-180
  
• Supriya Biswas, D. Chithra Prasad, Sudebkumar Prasant Pal:
  Algorithms for Convex Visibility Problems. 181-192
  
• Sandeep Sen:
  Lower Bounds for Parallel Algebraic Decision Trees, Complexity of Convex Hulls and Related Problems. 193-204
  

Concurrency

• Roberto M. Amadio, Sanjiva Prasad:
  Localities and Failures (Extended Abstract). 205-216
  
• V. Natarajan, Ivan Christoff, Linda Christoff, Rance Cleaveland:
  Priority and Abstraction in Process Algebra. 217-230
  
• K. Narayan Kumar, Paritosh K. Pandya:
  On the Computational Power of Operators in ICSP with Fairness. 231-242
  
• Wang Yi, Bengt Jonsson:
  Decidability of Timed Language-Inclusion for Networks of Real-Time Communicating Sequential Processes. 243-255
  

Invited Talk

• Lance Fortnow:
  My Favorite Ten Complexity Theorems of the Past Decade. 256-275
  

Unification

• Yuichi Kaji, Toru Fujiwara, Tadao Kasami:
  Solving a Unification Problem under Constrained Substitutions Using Tree Automata. 276-287
  
• R. Ramesh, I. V. Ramakrishnan, R. C. Sekar:
  Automata-Driven Efficient Subterm Unification. 288-299
  

Invited Talk

• Prabhakar Raghavan:
  Randomized Approximation Algorithms in Combinatorial Optimization. 300-317
  

Algorithms

• Vivek Arora, Santosh Vempala, Huzur Saran, Vijay V. Vazirani:
  A Limited-Backtrack Greedy Schema for Approximation Algorithms. 318-329
  
• Pierluigi Crescenzi, Luca Trevisan:
  On Approximation Scheme Preserving Reducability and Its Applications. 330-341
  
• Harry B. Hunt III, Madhav V. Marathe, Venkatesh Radhakrishnan, S. S. Ravi, Daniel J. Rosenkrantz, Richard Edwin Stearns:
  Approximation Schemes Using L-Reductions. 342-353
  
• Ashok Subramanian:
  An Explanation of Splaying. 354-365
  

Verification

• Jörg Desel:
  Proving Non-Reachabililty by Modulo-Place-Invariants. 366-377
  
• Edgar Knapp:
  Soundness and Completeness of UNITY Logic. 378-389
  
• Petr Savický, Ingo Wegener:
  Efficient Algorithms for the Transformation Betweeen Different Types of Binary Decision Diagrams. 390-401
  
• Michael Siegel, Frank A. Stomp:
  Extending the Limits of Sequentially Phased Reasoning. 402-413
  

Applied Algorithmics

• Vladimir Estivill-Castro, Derick Wood:
  Foundations for Faster External Sorting (Extended Abstract). 414-425
  
• John N. Hooker, V. Vinay:
  Branching Rules for Satisfiability (Extended Abstract). 426-437
  
• Deepak Kapur, Mahadevan Subramaniam:
  Using Linear Arithmetic Procedure for Generating Induction Schemes. 438-449