Theory and Applications of Models of Computation [recurso electrónico] : 9th Annual Conference, TAMC 2012, Beijing, China, May 16-21, 2012. Proceedings

Annotation This book constitutes the refereed proceedings of the 9th International Conference on Theory and Applications of Models of Computation, TAMC 2012, held in Beijing, China, in May 2012. The conference was combined with the Turing Lectures 2012, dedicated to celebrating Alan Turings unique impact on mathematics, computing, computer science, informatics, morphogenesis, philosophy, and the wider scientific world. Eight Turing Lectures were given at the TAMC 2012. The 40 revised full papers presented together with invited talks were carefully reviewed and selected from 86 submissions. The papers address 4 special sessions at TAMC 2012 which were algorithms and information in networks, complexity and cryptography, models of computing and networking, programming and verification Front Matter....Pages - On the Impact of Turing Machines....Pages 1-2 From Turing Machine to Morphogenesis: Forming and Informing Computation....Pages 3-10 Theory of Computation as an Enabling Tool for the Sciences....Pages 11-11 Interaction and Collective Intelligence on the Internet....Pages 12-22 What Computers Do: Model, Connect, Engage....Pages 23-26 R-Calculus: A Logical Inference System for Scientific Discovery....Pages 27-27 Quantum Computing: A Great Science in the Making....Pages 28-28 The Convergence of Social and Technological Networks....Pages 29-29 Principles of Network Computing....Pages 30-39 The Small Community Phenomenon in Networks: Models, Algorithms and Applications....Pages 40-49 Vertex-Pursuit in Hierarchical Social Networks....Pages 50-60 A Structural Approach to Prophecy Variables....Pages 61-71 An Assume/Guarantee Based Compositional Calculus for Hybrid CSP....Pages 72-83 Automatic Verification of Real-Time Systems with Rich Data: An Overview....Pages 84-93 Program Analysis Using Quantifier-Elimination Heuristics....Pages 94-108 Electron Tomography and Multiscale Biology....Pages 109-130 Constant-Time Approximation Algorithms for the Knapsack Problem....Pages 131-142 Lower Bounds of Shortest Vector Lengths in Random NTRU Lattices....Pages 143-155 Polynomial Time Construction of Ellipsoidal Approximations of Zonotopes Given by Generator Descriptions....Pages 156-163 Hardness and Approximation of the Asynchronous Border Minimization Problem....Pages 164-176 Asymptotic Limits of a New Type of Maximization Recurrence with an Application to Bioinformatics....Pages 177-188 Computing Bits of Algebraic Numbers....Pages 189-201 Approximating MAX SAT by Moderately Exponential and Parameterized Algorithms....Pages 202-213 Computing Error Distance of Reed-Solomon Codes....Pages 214-224 Coordination Mechanisms for Selfish Parallel Jobs Scheduling....Pages 225-236 Computationally-Fair Group and Identity-Based Key-Exchange....Pages 237-247 Timed Encryption with Application to Deniable Key Exchange....Pages 248-259 Online Makespan Scheduling of Linear Deteriorating Jobs on Parallel Machines....Pages 260-272 A Surprisingly Simple Way of Reversing Trace Distance via Entanglement....Pages 273-283 Constructions for Binary Codes Correcting Asymmetric Errors from Function Fields....Pages 284-294 Stopping Set Distributions of Algebraic Geometry Codes from Elliptic Curves....Pages 295-306 Energy-Efficient Network Routing with Discrete Cost Functions....Pages 307-318 An Algorithmic View on Multi-Related-Segments: A Unifying Model for Approximate Common Interval....Pages 319-329 The Worst Case Behavior of Randomized Gossip....Pages 330-345 Holographic Algorithms on Domain Size k > 2....Pages 346-359 A Refined Exact Algorithm for Edge Dominating Set....Pages 360-372 Finite Automata over Structures....Pages 373-384 Deterministic Distributed Data Aggregation under the SINR Model....Pages 385-399 Tensor Rank and Strong Quantum Nondeterminism in Multiparty Communication....Pages 400-411 Speed Scaling Problems with Memory/Cache Consideration....Pages 412-422 On the Amount of Nonconstructivity in Learning Formal Languages from Positive Data....Pages 423-434 Computing in the Fractal Cloud: Modular Generic Solvers for SAT and Q-SAT Variants....Pages 435-447 Online Optimization of Busy Time on Parallel Machines....Pages 448-460 Bisection (Band)Width of Product Networks with Application to Data Centers....Pages 461-472 Implicit Computation of Maximum Bipartite Matchings by Sublinear Functional Operations....Pages 473-486 A Game-Theoretic Approach for Balancing the Tradeoffs between Data Availability and Query Delay in Multi-hop Cellular Networks....Pages 487-497 Proving Liveness Property under Strengthened Compassion Requirements....Pages 498-508 Realizing Monads in Interaction Nets via Generic Typed Rules....Pages 509-524 Towards an Axiomatization of Simple Analog Algorithms....Pages 525-536 Multiple Usage of Random Bits in Finite Automata....Pages 537-547 Minimum Certificate Dispersal with Tree Structures....Pages 548-559 Improved FPT Algorithms for Rectilinear k -Links Spanning Path....Pages 560-571 FPT Results for Signed Domination....Pages 572-583 Submodular Minimization via Pathwidth....Pages 584-593 A Detailed Study of the Dominating Cliques Phase Transition in Random Graphs....Pages 594-603 An Application of 1-Genericity in the $\Pi^0_2$ Enumeration Degrees....Pages 604-620 Back Matter....Pages -