14. FSTTCS 1994: Madras, India

@proceedings{DBLP:conf/fsttcs/1994,
  editor    = {P. S. Thiagarajan},
  title     = {Foundations of Software Technology and Theoretical Computer Science,
               14th Conference, Madras, India, December 15-17, 1994, Proceedings},
  booktitle = {FSTTCS},
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = {880},
  year      = {1994},
  isbn      = {3-540-58715-2},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Invited Talk

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

Complexity Theory

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

Invited Talk

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

Algorithms

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

Invited Talk

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

Algorithms

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

Concurrency

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

Invited Talk

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

Unification

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

Invited Talk

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

Algorithms

• Vivek Arora, Santosh Vempala, Huzur Saran, Vijay V. Vazirani: A Limited-Backtrack Greedy Schema for Approximation Algorithms. 318-329 BibTeX
• Pierluigi Crescenzi, Luca Trevisan: On Approximation Scheme Preserving Reducability and Its Applications. 330-341 BibTeX
• 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 BibTeX
• Ashok Subramanian: An Explanation of Splaying. 354-365 BibTeX

Verification

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

Applied Algorithmics

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