Skip to main content
SpringerLink
Log in
SpringerLink
Log in

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

  • Conference proceedings
  • © 2004

Overview

Editors:
  1. Jean-Jacques Levy

    1. INRIA, France

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Ernst W. Mayr

    1. Technische Universität München, Germany

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. John C. Mitchell

    1. Stanford University, USA

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

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

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 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

Licence this eBook for your library

Institutional subscriptions

Table of contents (50 papers)

  1. Front Matter

    Pages i-xiv
    Download chapter PDF

  3. 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. Reversible Circuit Realizations of Boolean Functions

      • Alex Brodsky
      Pages 67-80

    5. Resource Bounded Immunity and Simplicity

      • Toshio Suzuki, Tomoyuki Yamakami
      Pages 81-96

    6. Degree Bounds on Polynomials and Relativization Theory

      • Holger Spakowski, Rahul Tripathi
      Pages 97-110

    7. The Firing Squad Synchronization Problem with Many Generals for One-Dimensional CA

      • Hubert Schmid, Thomas Worsch
      Pages 111-124

    8. A Matrix Q-Analogue of the Parikh Map

      • Omer Egecioglu, Oscar H. Ibarra
      Pages 125-138

    9. The Inherent Queuing Delay of Parallel Packet Switches

      • Hagit Attiya, David Hay
      Pages 139-152

    10. 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

    11. Truthful Mechanisms for Generalized Utilitarian Problems

      • G. Melideo, P. Penna, G. Proietti, R. Wattenhofer, P. Widmayer
      Pages 167-180

    12. The Driving Philosophers

      • S. Baehni, R. Baldoni, R. Guerraoui, B. Pochon
      Pages 181-194

    13. Engineering an External Memory Minimum Spanning Tree Algorithm

      • Roman Dementiev, Peter Sanders, Dominik Schultes, Jop Sibeyn
      Pages 195-208

    14. 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

    15. Approximation Algorithms for Mixed Fractional Packing and Covering Problems

      • Klaus Jansen
      Pages 223-236
Back to top

Keywords

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

Publish with us

Policies and ethics

Back to top

Search

Navigation