Ebook: 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 addressing these foundational questions, as well as 4 papers by outstanding invited speakers. These papers were presented at the 2nd IFIP International Conference on Theoretical Computer Science (TCS 2002), which was held in conjunction with the 17th World Computer Congress, sponsored by the International Federation for Information Processing (IFIP), and which convened in Montréal, Québec, Canada in August 2002.

---

---

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

---

Content:
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
....