Foundations of Information Technology in the Era of Network and Mobile Computing

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.

Inhalt

Preface. External Referees. Track 1: Algorithms, Complexity and Models of Computation. Invited Papers. Power of Quantum Entanglement; J. Gruska, et al. Information Networks, Link Analysis, and Temporal Dynamics; J. Kleinberg. Contributed Papers. Geometric Separation and Exact Solutions for the Parameterized Independent Set Problem on Disk Graphs; J. Alber, J. Fiala. Bin-Packing with Fragile Objects; N. Bansal, et al. Lower and Upper Bounds for Tracking Mobile Users; S. Bespamyatnikh, et al. On the Enumerability of the Determinant and the Rank; A. Beygelzimer, M. Ogihara. On the Symmetric Range Assignment Problem in Wireless Ad Hoc Networks; D.M. Blough, et al. Parity Graph-driven Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication; B. Bollig, et al. Computability of Linear Equations; V. Brattka, M. Ziegler. Hierarchy Among Automata on Linear Orderings; V. Bruyére, O. Carton. Symmetric Connectivity with Minimum Power Consumption in Radio Networks; G. Calinescu, et al. A Modified Recursive Triangular Factorization for Cauchy-like Systems; Z. Chen. Algorithmic Complexity of Protein Identification: Searching in Weighted Strings; M. Cieliebak, et al. An Efficient Parallel Pointer Machine Algorithm for the NCA Problem; A.D. Palú, et al. Randomized Dining Philosophers without Fairness Assumption; M. Duflot, et al. Guarding Galleries and Terrains; A. Efrat, S. Har-Peled. Gossiping with Unit Messages in Known Radio Networks; L. Gasieniec, I. Potapov. Memoryless Search Algorithms in a Network with Faulty Advice; N. Hanusse, et al. Lower Bounds and the Hardness of Counting Properties; L.A. Hemaspaandra, M. Thakur. Framework for Analyzing Garbage Collection; M. Hertz, etal. One-Way Permutations and Self-Witnessing Languages; C.M. Homan, M. Thakur. Approximation Algorithms for General Packing Problems with Modified Logarithmic Potential Function; K. Jansen, H. Zhang. On Randomness and Infinity; G. Lafitte. Server Placements, Roman Domination and other Dominating Set Variants; A. Pagourtzis, et al. A Linear Time Algorithm for Finding Tree 3-Spanner on 2-Trees; B.S. Panda, S.K. Das. Exact Complexity of Exact-Four-Colorability and of the Winner Problem for Young Elections; J. Rothe, et al. Quantum NP and Quantum Hierarchy; T. Yamakami. Probabilistically Checkable Proofs the Easy Way; M. Zimand. Track 2: Logic, Semantics, Specification and Verification. Invited Papers. XML Web Services: The Global Computer? A. Gordon. Micro Mobile Programs; C. Gunter. Contributed Papers. Checking Polynomial Time Complexity with Types; P. Baillot. Boundary Inference for Enforcing Security Policies in Mobile Ambients; C. Braghin, et al. Decidability and Tractability of Problems in Object-Based Graph Grammars; A. Brum Loreto, et al. Coverage of Implementations by Simulating Specifications; H. Chockler, O. Kupferman. TQL Algebra and its Implementation; G. Conforti, et al. Model Checking Birth and Death; D. Distefano, et al. Phantom Types and Subtyping; M. Fluet, R. Pucella. On the Weakest Failure Detector for Non-Blocking Atomic Commit; R. Guerraoui, P. Kouznetsov. Combining Computational Effects: commutativity & sum; M. Hyland, et al. Optimal-Reachability and Control for Acyclic Weighted Timed Automata; S. La Torre, et al. Substructural Verification and Computational Feasibility; D. Leivant. An Improved System of Intersection Types for Explicit Substitutions; D. Dougherty, et al. About Compositional