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

Front Matter....Pages i-xiv
Front Matter....Pages 1-1
Power of Quantum Entanglement....Pages 3-22
Information Networks, Link Analysis, and Temporal Dynamics....Pages 23-25
Geometric Separation and Exact Solutions for the Parameterized Independent Set Problem on Disk Graphs....Pages 26-37
Bin-Packing with Fragile Objects....Pages 38-46
Lower and Upper Bounds for Tracking Mobile Users....Pages 47-58
On the Enumerability of the Determinant and the Rank....Pages 59-70
On the Symmetric Range Assignment Problem in Wireless Ad Hoc Networks....Pages 71-82
Parity Graph-Driven Read-Once Branching Programs and An Exponential Lower Bound for Integer Multiplication....Pages 83-94
Computability of Linear Equations....Pages 95-106
Hierarchy Among Automata on Linear Orderings....Pages 107-118
Symmetric Connectivity with Minimum Power Consumption in Radio Networks....Pages 119-130
A Modified Recursive Triangular Factorization for Cauchy-Like Systems....Pages 131-142
Algorithmic Complexity of Protein Identification: Searching in Weighted Strings....Pages 143-156
An Efficient Parallel Pointer Machine Algorithm for the NCA Problem....Pages 157-168
Randomized Dining Philosophers without Fairness Assumption....Pages 169-180
Guarding Galleries and Terrains....Pages 181-192
Gossiping with Unit Messages in Known Radio Networks....Pages 193-205
Memoryless Search Algorithms in a Network with Faulty Advice....Pages 206-216
Lower Bounds and the Hardness of Counting Properties....Pages 217-229
Framework for Analyzing Garbage Collection....Pages 230-242
Front Matter....Pages 1-1
One-Way Permutations and Self-Witnessing Languages....Pages 243-254
Approximation Algorithms for General Packing Problems with Modified Logarithmic Potential Function....Pages 255-266
On Randomness and Infinity....Pages 267-279
Server Placements, Roman Domination and Other Dominating Set Variants....Pages 280-291
A Linear Time Algorithm for Finding Tree 3-Spanner on 2-Trees....Pages 292-309
Exact Complexity of Exact-Four-Colorability and of the Winner Problem for Young Elections....Pages 310-322
Quantum NP and a Quantum Hierarchy....Pages 323-336
Probabilistically Checkable Proofs the Easy Way....Pages 337-351
Front Matter....Pages 353-353
XML Web Services: The Global Computer?....Pages 355-355
Micro Mobile Programs....Pages 356-369
Checking Polynomial Time Complexity with Types....Pages 370-382
Boundary Inference for Enforcing Security Policies in Mobile Ambients....Pages 383-395
Decidability and Tractability of Problems in Object-Based Graph Grammars....Pages 396-408
Coverage of Implementations by Simulating Specifications....Pages 409-421
TQL Algebra and Its Implementation....Pages 422-434
Model Checking Birth and Death....Pages 435-447
Phantom Types and Subtyping....Pages 448-460
On the Weakest Failure Detector for Non-Blocking Atomic Commit....Pages 461-473
Combining Computational Effects: Commutativity and Sum....Pages 474-484
Optimal-Reachability and Control for Acyclic Weighted Timed Automata....Pages 485-497
Front Matter....Pages 353-353
Substructural Verification and Computational Feasibility....Pages 498-510
An Improved System of Intersection Types for Explicit Substitutions....Pages 511-523
About Compositional Analysis of π-Calculus Processes....Pages 524-536
A Randomized Distributed Encoding of the π-Calculus with Mixed Choice....Pages 537-549
On Reduction Semantics for the Push and Pull Ambient Calculus....Pages 550-562
Safe Dynamic Binding in the Join Calculus....Pages 563-575
Vectorial Languages and Linear Temporal Logic....Pages 576-587
A Bound on Attacks on Authentication Protocols....Pages 588-600
Responsive Bisimulation....Pages 601-612
Back Matter....Pages 613-613