Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science

21st Conference, Bangalore, India, December 13-15, 2001, Proceedings

  • Conference proceedings
  • © 2001

Overview

Editors:
  1. Ramesh Hariharan

    1. Department of Computer Science and Automation, Indian Institute of Science, Bangalore, India

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. V. Vinay

    1. Department of Computer Science and Automation, Indian Institute of Science, Bangalore, India

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Madhavan Mukund

    1. Chennai Mathematical Institute, Chennai, India

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 2245)

Included in the following conference series:

Conference proceedings info: FSTTCS 2001.

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

eBook USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

About this book

This volume contains the proceedings of the 21st international conference on the Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2001), organized under the auspices of the Indian Association for Research in Computing Science (IARCS). This year’s conference attracted 73 submissions from 20 countries. Each s- mission was reviewed by at least three independent referees. In a departure from previous conferences, the ?nal selection of the papers making up the program was done through an electronic discussion spanning two weeks, without a physical meeting of the Program Committee (PC). Since the PC of FSTTCS is distributed across the globe, it is very di?cult to ?x a meeting whose time and venue is convenient for a substantial fraction of the PC. Given this, it was felt that an electronic discussion would enable all members to participate on a more equal footing in the ?nal selection. All reviews, scores, and comments were posted on a secure website, with a mechanism for making updates and automatically sending noti?cations by email to relevant members of the PC. All PC members participated actively in the discussion. The general feedback on the arrangement was very positive, so we hope to continue this in future years. We had ?ve invited speakers this year: Eric Allender, Sanjeev Arora, David Harel, Colin Stirling, and Uri Zwick. We thank them for having readily accepted our invitation to talk at the conference and for providing abstracts (and even full papers) for the proceedings.

Keywords

Table of contents (28 papers)

  1. Front Matter

    Pages I-XI
    Download chapter PDF

  3. Contributed Papers

    1. Hard Sets and Pseudo-random Generators for Constant Depth Circuits

      • Manindra Agrawal
      Pages 58-69

    2. The First-Order Isomorphism Theorem

      • Manindra Agrawal
      Pages 70-82

    3. Thresholds and Optimal Binary Comparison Search Trees

      • Richard Anderson, Sampath Kannan, Howard Karloff, Richard E. Ladner
      Pages 83-95

    4. Distributed LTL Model Checking Based on Negative Cycle Detection

      • Luboš Brim, Ivana Černá, Pavel Krčál, Radek Pelánek
      Pages 96-107

    5. Computability and Complexity Results for a Spatial Assertion Language for Data Structures

      • Cristiano Calcagno, Hongseok Yang, Peter W. O’Hearn
      Pages 108-119

    6. Using Nondeterminism to Design Efficient Deterministic Algorithms

      • Jianer Chen, Donald K. Friesen, Weijia Jia, Iyad A. Kanj
      Pages 120-131

    7. Liveness Verification of Reversal-Bounded Multicounter Machines with a Free Counter

      • Zhe Dang, Oscar H. Ibarra, Pierluigi San Pietro
      Pages 132-143

    8. A Mechanically Verified Compiling Specification for a Lisp Compiler

      • Axel Dold, Vincent Vialard
      Pages 144-155

    9. Beyond Regular Model Checking

      • Dana Fisman, Amir Pnueli
      Pages 156-170

    10. Relations Between Communication Complexity, Linear Arrangements, and Computational Complexity

      • Jürgen Forster, Matthias Krause, Satyanarayana V. Lokam, Rustam Mubarakzjanov, Niels Schmitt, Hans Ulrich Simon
      Pages 171-182

    11. Optimal, Output-Sensitive Algorithms for Constructing Upper Envelope of Line Segments in Parallel

      • Neelima Gupta, Sumit Chopra, Sandeep Sen
      Pages 183-194

    12. List Decoding from Erasures: Bounds and Code Constructions

      • Venkatesan Guruswami
      Pages 195-206

    13. Verification of a Leader Election Algorithm in Timed Asynchronous Systems

      • Neeraj Jaggi, K. Gopinath
      Pages 207-218

    14. Efficient Addition on Field Programmable Gate Arrays

      • Andreas Jakoby, Christian Schindelhauer
      Pages 219-231
Back to top

Other volumes

  1. FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science

Editors and Affiliations

  • Department of Computer Science and Automation, Indian Institute of Science, Bangalore, India

    Ramesh Hariharan, V. Vinay

  • Chennai Mathematical Institute, Chennai, India

    Madhavan Mukund

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation