Foundations of information technology in the era of network and mobile computing : IFIP 17th World Computer Congress--TC1 stream/2nd IFIP International Conference on Theoretical Computer Science (TCS 2002), August 25-30, 2002, Montréal, Québec, Canada /
Foundations of Information Technology in the Era of Network and Mobile Computing is presented in two distinct but interrelated tracks: -Algorithms, Complexity and Models of Computation; -Logic, Semantics, Specification and Verification. This volume contains 45 original and significant contributions...
| Corporate Authors: | , , |
|---|---|
| Other Authors: | , , |
| Format: | Conference Proceeding eBook |
| Language: | English |
| Published: |
Boston :
Kluwer Academic Publishers,
[2002]
|
| Series: | International Federation for Information Processing (Series) ;
96. |
| Subjects: | |
| Online Access: | Connect to the full text of this electronic book |
Table of Contents:
- Preface
- External Referees
- Track 1: Algorithms, Complexity and Models of Computation
- Invited Papers
- Power of Quantum Entanglement / Jozef Gruska, Hiroshi Imai, Keiji Matsumoto
- Information Networks, Link Analysis, and Temporal Dynamics / Jon Kleinberg
- Contributed Papers
- Geometric Separation and Exact Solutions for the Parameterized Independent Set Problem on Disk Graphs / Jochen Alber, Jiri Fiala
- Bin-Packing with Fragile Objects / Nikhil Bansal, Zhen Liu, Arvind Sankar
- Lower and Upper Bounds for Tracking Mobile Users / S. Bespamyatnikh, B. Bhattacharya, D. Kirkpatrick, M. Segal
- On the Enumerability of the Determinant and the Rank / Alina Beygelzimer, Mitsunori Ogihara
- On the Symmetric Range Assignment Problem in Wireless Ad Hoc Networks / Douglas M. Blough, Mauro Leoncini, Giovanni Resta, Paolo Santi
- Parity Graph-driven Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication / Beate Bollig, Stephan Waack, Philipp Woelfel
- Computability of Linear Equations / Vasco Brattka, Martin Ziegler
- Hierarchy Among Automata on Linear Orderings / Vronique Bruyere, Olivier Carton
- Symmetric Connectivity with Minimum Power Consumption in Radio Networks / G. Calinescu, I.I. Mandoiu, A. Zelikovsky
- A Modified Recursive Triangular Factorization for Cauchy-like Systems / Z. Chen
- Algorithmic Complexity of Protein Identification: Searching in Weighted Strings / M. Cieliebak, T. Erlebach, Z. Liptak, J. Stoye, E. Welzl
- An Efficient Parallel Pointer Machine Algorithm for the NCA Problem / Alessandro Dal Palu, Enrico Pontelli, Desh Ranjan
- Randomized Dining Philosophers without Fairness Assumption / Marie Duflot, Laurent Fribourg, Claudine Picaronny
- Guarding Galleries and Terrains / Alon Efrat, Sariel Har-Peled
- Gossiping with Unit Messages in Known Radio Networks / Leszek Gasieniec, Igor Potapov
- Memoryless Search Algorithms in a Network with Faulty Advice / N. Hanusse, D. Kavvadias, E. Kranakis, D. Krizane
- Lower Bounds and the Hardness of Counting Properties / Lane A. Hemaspaandra, Mayur Thakur
- Framework for Analyzing Garbage Collection / Matthew Hertz, Neil Immerman, J Eliot B Moss
- One-Way Permutations and Self-Witnessing Languages / Christopher M. Homan, Mayur Thakur
- Approximation Algorithms for General Packing Problems with Modified Logarithmic Potential Function / Klaus Jansen, Hu Zhang
- On Randomness and Infinity / Gregory Lafitte
- Server Placements, Roman Domination and other Dominating Set Variants / A. Pagourtzis, P. Penna, K. Schlude, K. Steinhofel, D. Taylor, P. Widmayer
- A Linear Time Algorithm for Finding Tree 3-Spanner on 2-Trees / B. S. Panda, Sajal K. Das
- Exact Complexity of Exact-Four-Colorability and of the Winner Problem for Young Elections / Joerg Rothe, Holger Spakowski, Joerg Vogel
- Quantum NP and Quantum Hierarchy / Tomoyuki Yamakami
- Probabilistically Checkable Proofs the Easy Way / Marius Zimand
- Track 2: Logic, Semantics, Specification and Verification
- Invited Papers
- XML Web Services: The Global Computer? / Andrew Gordon
- Micro Mobile Programs / Carl Gunter
- Contributed Papers
- Checking Polynomial Time Complexity with Types / Patrick Baillot
- Boundary Inference for Enforcing Security Policies in Mobile Ambients / Chiara Braghin, Agostino Cortesi, Riccardo Focardi, Steffen van Bakel
- Decidability and Tractability of Problems in Object-Based Graph Grammars / Aline Brum Loreto, Leila Ribeiro, Laira Vieira Toscani
- Coverage of Implementations by Simulating Specifications / Hana Chockler, Orna Kupferman
- TQL Algebra and its Implementation / Giovanni Conforti, Orlando Ferrara, Giorgio Ghelli
- Model Checking Birth and Death / Dino Distefano, Arend Rensink, Joost-Pieter Katoen
- Phantom Types and Subtyping / Matthew Fluet, Riccardo Pucella
- On the Weakest Failure Detector for Non-Blocking Atomic Commit / Rachid Guerraoui, Petr Kouznetsov
- Combining Computational Effects: commutativity & sum / Martin Hyland, Gordon Plotkin, John Power
- Optimal-Reachability and Control for Acyclic Weighted Timed Automata / Salvatore La Torre, Supratik Mukhopadhyay, Aniello Murano
- Substructural Verification and Computational Feasibility / Daniel Leivant
- An Improved System of Intersection Types for Explicit Substitutions / Dan Dougherty, Stephane Lengrand, Pierre Lescanne
- About Compositional Analysis of Pi-Calculus Processes / Fabio Martinelli
- A Randomized Distributed Encoding of the Pi-Calculus with Mixed Choice / Catuscia Palamidessi, Oltea Milhaela Herescu
- On Reduction Semantics for the Push and Pull Ambient Calculus / C.C. Phillips, M.G. Vigliotti
- Safe Dynamic Binding in the Join Calculus / Alan Schmitt
- Vectorial Languages and Linear Temporal Logic / Olivier Serre
- A Bound on Attacks on Authentication Protocols / Scott D. Stoller
- Responsive Bisimulation Xiaogang Zhang, John Potter
- Author Index.