Skip to main content
SpringerLink
Log in

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

22nd Conference Kanpur, India, December 12-14, 2002, Proceedings

  • Conference proceedings
  • © 2002

Overview

Editors:
  1. Manindra Agrawal

    1. Department of Computer Science and Engineering, Indian Institute of Technology, Kanpur, India

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Anil Seth

    1. Department of Computer Science and Engineering, Indian Institute of Technology, Kanpur, 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 2556)

Included in the following conference series:

Conference proceedings info: FSTTCS 2002.

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

Access this book

Log in via an institution
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

Table of contents (31 papers)

  1. Front Matter

    Pages I-XI
    Download chapter PDF

  2. Invited Papers

    1. Primality Testing with Gaussian Periods

      • H. W. Lenstra Jr.
      Pages 1-1

    2. From Hilbert Spaces to Dilbert Spaces: Context Semantics Made Simple

      • Harry G. Mairson
      Pages 2-17

    3. Encoding Generic Judgments

      • Dale Miller, Alwen Tiu
      Pages 18-32

    4. Model Checking Algol-Like Languages Using Game Semantics

      • C. -H. L. Ong
      Pages 33-36

    5. Modeling Software: From Theory to Practice

      • Margus Veanes
      Pages 37-46

  3. Contributed Papers

    1. Local Normal Forms for Logics over Traces

      • Bharat Adsul, Milind Sohoni
      Pages 47-58

    2. On the Hardness of Constructing Minimal 2-Connected Spanning Subgraphs in Complete Graphs with Sharpened Triangle Inequality

      • Hans-Joachim Böckenhauer, Dirk Bongartz, Juraj Hromkovič, Ralf Klasing, Guido Proietti, Sebastian Seibert et al.
      Pages 59-70

    3. Communication Interference in Mobile Boxed Ambients

      • Michele Bugliesi, Silvia Crafa, Massimo Merro, Vladimiro Sassone
      Pages 71-84

    4. The Seal Calculus Revisited: Contextual Equivalence and Bisimilarity

      • Giuseppe Castagna, Francesco Zappa Nardelli
      Pages 85-96

    5. Composing Strand Spaces

      • Federico Crazzolara, Glynn Winskel
      Pages 97-108

    6. Generalising Automaticity to Modal Properties of Finite Structures

      • A. Dawar, S. Kreutzer
      Pages 109-120

    7. An Automata-Theoretic Approach to Constraint LTL

      • Stéphane Demri, Deepak D’souza
      Pages 121-132

    8. Hardness Results for Multicast Cost Sharing

      • Joan Feigenbaum, Arvind Krishnamurthy, Rahul Sami, Scott Shenker
      Pages 133-144

    9. How to Compose Presburger-Accelerations: Applications to Broadcast Protocols

      • Alain Finkel, Jérôme Leroux
      Pages 145-156

    10. State Space Reductions for Alternating Büchi Automata Quotienting by Simulation Equivalences

      • Carsten Fritz, Thomas Wilke
      Pages 157-168

    11. Algorithmic Combinatorics Based on Slicing Posets

      • Vijay K. Garg
      Pages 169-181

    12. Pattern Matching for Arc-Annotated Sequences

      • Jens Gramm, Jiong Guo, Rolf Niedermeier
      Pages 182-193

    13. Knowledge over Dense Flows of Time (from a Hybrid Point of View)

      • Bernhard Heinemann
      Pages 194-205

    14. The Complexity of the Inertia

      • Thanh Minh Hoang, Thomas Thierauf
      Pages 206-217
Back to top

Other volumes

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

Keywords

About this book

This volume consists of the proceedings of the 22nd International Conference on the Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2002), organized under the auspices of the Indian Association for Research in Computing Science (IARCS). The conference was held at the Indian Institute of Technology, Kanpur during December 12–14, 2002. The conference attracted 108 submissions (of which two were withdrawn). Of these, a total of 26 papers were selected for presentation in the conference. As in the last year, the PC meeting was held electronically (stretching over nearly three weeks in August 2002) and was a great success. In addition to the contributed papers, we had ?ve invited speakers this year: Hendrik Lenstra, Jr., Harry Mairson, Dale Miller, Chih-Hao Luke Ong, and Margus Veanes. We thank them for accepting our invitation and for providing abstracts (or even full papers) for the proceedings. Two workshops were organized in conjunction with the conference – both in Kanpur. A workshop on Parameterized Complexity was held during December 10–11, organized by Mike Fellows and Venkatesh Raman. The second workshop actually consisted of three miniworkshops: on Coding Theory by Madhu Sudan; on Finite Field Algorithms by Hendrik Lenstra, Jr.; and on Sieve Theory by R. Balasubramanian. We wish to thank all the reviewers and PC members who contributed greatly to making the conference a success. We also wish to thank the team at Springer- Verlag for their help in preparing the proceedings.

Editors and Affiliations

  • Department of Computer Science and Engineering, Indian Institute of Technology, Kanpur, India

    Manindra Agrawal, Anil Seth

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation