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. |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.
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
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.
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.
Power of Quantum Entanglement.- Information Networks, Link Analysis, and Temporal Dynamics.- Geometric Separation and Exact Solutions for the Parameterized Independent Set Problem on Disk Graphs.- Bin-Packing with Fragile Objects.- Lower and Upper Bounds for Tracking Mobile Users.- On the Enumerability of the Determinant and the Rank.- On the Symmetric Range Assignment Problem in Wireless Ad Hoc Networks.- Parity Graph, driven Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication.- Computability of Linear Equations.- Hierarchy Among Automata on Linear Orderings.- Symmetric Connectivity with Minimum Power Consumption in Radio Networks.- A Modified Recursive Triangular Factorization for Cauchy-like Systems.- Algorithmic Complexity of Protein Identification: Searching in Weighted Strings.- An Efficient Parallel Pointer Machine Algorithm for the NCA Problem.- Randomized Dining Philosophers without Fairness Assumption.- Guarding Galleries and Terrains.- Gossiping with Unit Messages in Known Radio Networks.- Memoryless Search Algorithms in a Network with Faulty Advice.- Lower Bounds and the Hardness of Counting Properties.- Framework for Analyzing Garbage Collection.- One-Way Permutations and Self-Witnessing Languages.- Approximation Algorithms for General Packing Problems with Modified Logarithmic Potential Function.- On Randomness and Infinity.- Server Placements, Roman Domination and other Dominating Set Variants.- A Linear Time Algorithm for Finding Tree 3-Spanner on 2-Trees.- Exact Complexity of Exact-Four-Colorability and of the Winner Problem for Young Elections.- Quantum NP and Quantum Hierarchy.- Probabilistically Checkable Proofs the Easy Way.- XML Web Services: The Global Computer?.- Micro Mobile Programs.- Checking Polynomial TimeComplexity with Types.- Boundary Inference for Enforcing Security Policies in Mobile Ambients.- Decidability and Tractability of Problems in Object-Based Graph Grammars.- Coverage of Implementations by Simulating Specifications.- TQL Algebra and its Implementation.- Model Checking Birth and Death.- Phantom Types and Subtyping.- On the Weakest Failure Detector for Non-Blocking Atomic Commit.- Combining Computational Effects: commutativity & sum.- Optimal-Reachability and Control for Acyclic Weighted Timed Automata.- Substructural Verification and Computational Feasibility.- An Improved System of Intersection Types for Explicit Substitutions.- About Compositional Analysis of Pi-Calculus Processes.- A Randomized Distributed Encoding of the Pi-Calculus with Mixed Choice.- On Reduction Semantics for the Push and Pull Ambient Calculus.- Safe Dynamic Binding in the Join Calculus.- Vectorial Languages and Linear Temporal Logic.- A Bound on Attacks on Authentication Protocols.- Responsive Bisimulation.- Author Index.
Inhaltsverzeichnis
Power of Quantum Entanglement.- Information Networks, Link Analysis, and Temporal Dynamics.- Geometric Separation and Exact Solutions for the Parameterized Independent Set Problem on Disk Graphs.- Bin-Packing with Fragile Objects.- Lower and Upper Bounds for Tracking Mobile Users.- On the Enumerability of the Determinant and the Rank.- On the Symmetric Range Assignment Problem in Wireless Ad Hoc Networks.- Parity Graph, driven Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication.- Computability of Linear Equations.- Hierarchy Among Automata on Linear Orderings.- Symmetric Connectivity with Minimum Power Consumption in Radio Networks.- A Modified Recursive Triangular Factorization for Cauchy-like Systems.- Algorithmic Complexity of Protein Identification: Searching in Weighted Strings.- An Efficient Parallel Pointer Machine Algorithm for the NCA Problem.- Randomized Dining Philosophers without Fairness Assumption.- Guarding Galleries and Terrains.- Gossiping with Unit Messages in Known Radio Networks.- Memoryless Search Algorithms in a Network with Faulty Advice.- Lower Bounds and the Hardness of Counting Properties.- Framework for Analyzing Garbage Collection.- One-Way Permutations and Self-Witnessing Languages.- Approximation Algorithms for General Packing Problems with Modified Logarithmic Potential Function.- On Randomness and Infinity.- Server Placements, Roman Domination and other Dominating Set Variants.- A Linear Time Algorithm for Finding Tree 3-Spanner on 2-Trees.- Exact Complexity of Exact-Four-Colorability and of the Winner Problem for Young Elections.- Quantum NP and Quantum Hierarchy.- Probabilistically Checkable Proofs the Easy Way.- XML Web Services: The Global Computer?.- Micro Mobile Programs.- Checking Polynomial TimeComplexity with Types.- Boundary Inference for Enforcing Security Policies in Mobile Ambients.- Decidability and Tractability of Problems in Object-Based Graph Grammars.- Coverage of Implementations by Simulating Specifications.- TQL Algebra and its Implementation.- Model Checking Birth and Death.- Phantom Types and Subtyping.- On the Weakest Failure Detector for Non-Blocking Atomic Commit.- Combining Computational Effects: commutativity & sum.- Optimal-Reachability and Control for Acyclic Weighted Timed Automata.- Substructural Verification and Computational Feasibility.- An Improved System of Intersection Types for Explicit Substitutions.- About Compositional Analysis of Pi-Calculus Processes.- A Randomized Distributed Encoding of the Pi-Calculus with Mixed Choice.- On Reduction Semantics for the Push and Pull Ambient Calculus.- Safe Dynamic Binding in the Join Calculus.- Vectorial Languages and Linear Temporal Logic.- A Bound on Attacks on Authentication Protocols.- Responsive Bisimulation.- Author Index.
Klappentext
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.
