Skip to main content
  • Conference proceedings
  • © 2004

Exploring New Frontiers of Theoretical Informatics

IFIP 18th World Computer Congress TC1 3rd International Conference on Theoretical Computer Science (TCS2004) 22–27 August 2004 Toulouse, France

Part of the book series: IFIP Advances in Information and Communication Technology (IFIPAICT, volume 155)

Buy it now

Buying options

eBook USD 149.00
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 199.00
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

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

Table of contents (50 papers)

  1. Front Matter

    Pages i-xiv
  2. Track (1) on Algorithms, Complexity, and Models of Computation

    1. Looking Inside Aεs and Bεs

      • Ilia Toli, Alberto Zanoni
      Pages 23-36
    2. Remove key Escrow from the Identity-Based Encryption System

      • Zhaohui Cheng, Richard Comley, Luminita Vasiu
      Pages 37-50
    3. A Randomised Algorithm for Checking The Normality of Cryptographic Boolean Functions

      • An Braeken, Christopher Wolf, Bart Preneel
      Pages 51-66
    4. Resource Bounded Immunity and Simplicity

      • Toshio Suzuki, Tomoyuki Yamakami
      Pages 81-96
    5. Degree Bounds on Polynomials and Relativization Theory

      • Holger Spakowski, Rahul Tripathi
      Pages 97-110
    6. A Matrix Q-Analogue of the Parikh Map

      • Omer Egecioglu, Oscar H. Ibarra
      Pages 125-138
    7. The Inherent Queuing Delay of Parallel Packet Switches

      • Hagit Attiya, David Hay
      Pages 139-152
    8. Efficient Protocols for Computing the Optimal Swap Edges of a Shortest Path Tree

      • Paola Flocchini, Antonio Mesa Enriques, Linda Pagli, Giuseppe Prencipe, Nicola Santoro
      Pages 153-166
    9. Truthful Mechanisms for Generalized Utilitarian Problems

      • G. Melideo, P. Penna, G. Proietti, R. Wattenhofer, P. Widmayer
      Pages 167-180
    10. The Driving Philosophers

      • S. Baehni, R. Baldoni, R. Guerraoui, B. Pochon
      Pages 181-194
    11. Engineering an External Memory Minimum Spanning Tree Algorithm

      • Roman Dementiev, Peter Sanders, Dominik Schultes, Jop Sibeyn
      Pages 195-208
    12. Scheduling With Release Times and Deadlines on A Minimum Number of Machines

      • Mark Cieliebak, Thomas Erlebach, Fabian Hennecke, Birgitta Weber, Peter Widmayer
      Pages 209-222

About this book

In recent years, IT application scenarios have evolved in very innovative ways. Highly distributed networks have now become a common platform for large-scale distributed programming, high bandwidth communications are inexpensive and widespread, and most of our work tools are equipped with processors enabling us to perform a multitude of tasks. In addition, mobile computing (referring specifically to wireless devices and, more broadly, to dynamically configured systems) has made it possible to exploit interaction in novel ways. To harness the flexibility and power of these rapidly evolving, interactive systems, there is need of radically new foundational ideas and principles; there is need to develop the theoretical foundations required to design these systems and to cope with the many complex issues involved in their construction; and there is need to develop effective principles for building and analyzing such systems.

Reflecting the diverse and wide spectrum of topics and interests within the theoretical computer science community, Exploring New Frontiers of Theoretical Informatics, is presented in two distinct but interrelated tracks:

-Algorithms, Complexity and Models of Computation,
-Logic, Semantics, Specification and Verification.

Exploring New Frontiers of Theoretical Informatics contains 46 original and significant contributions addressing these foundational questions, as well as 4 papers by outstanding invited speakers. These papers were presented at the 3rd IFIP International Conference on Theoretical Computer Science (TCS 2004), which was held in conjunction with the 18th World Computer Congress in Toulouse, France in August 2004 and sponsored by the International Federation for Information Processing (IFIP).

Editors and Affiliations

  • INRIA, France

    Jean-Jacques Levy

  • Technische Universität München, Germany

    Ernst W. Mayr

  • Stanford University, USA

    John C. Mitchell

Bibliographic Information

  • Book Title: Exploring New Frontiers of Theoretical Informatics

  • Book Subtitle: IFIP 18th World Computer Congress TC1 3rd International Conference on Theoretical Computer Science (TCS2004) 22–27 August 2004 Toulouse, France

  • Editors: Jean-Jacques Levy, Ernst W. Mayr, John C. Mitchell

  • Series Title: IFIP Advances in Information and Communication Technology

  • DOI: https://doi.org/10.1007/b98989

  • Publisher: Springer New York, NY

  • eBook Packages: Springer Book Archive

  • Copyright Information: IFIP International Federation for Information Processing 2004

  • Hardcover ISBN: 978-1-4020-8140-8Due: 27 July 2004

  • Softcover ISBN: 978-1-4419-5486-2Published: 14 December 2011

  • eBook ISBN: 978-1-4020-8141-5Published: 11 April 2006

  • Series ISSN: 1868-4238

  • Series E-ISSN: 1868-422X

  • Edition Number: 1

  • Number of Pages: XIV, 676

  • Topics: Theory of Computation, The Computer Industry, Computer Applications

Buy it now

Buying options

eBook USD 149.00
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 199.00
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