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. 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 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, 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. 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 Montreal, Quebec, Canada in August 2002.