Theory and Applications of Models of Computation

1. Front Matter

   PDF

2. Turing Lectures 2012

   1. On the Impact of Turing Machines

      • John Hopcroft

      Pages 1-2

   2. From Turing Machine to Morphogenesis: Forming and Informing Computation

      • S. Barry Cooper

      Pages 3-10

   3. Theory of Computation as an Enabling Tool for the Sciences

      • Richard M. Karp

      Pages 11-11

   4. Interaction and Collective Intelligence on the Internet

      • Deyi Li, Liwei Huang

      Pages 12-22

   5. What Computers Do: Model, Connect, Engage

      • Butler Lampson

      Pages 23-26

   6. R-Calculus: A Logical Inference System for Scientific Discovery

      • Wei Li

      Pages 27-27

   7. Quantum Computing: A Great Science in the Making

      • Andrew Chi-Chih Yao

      Pages 28-28

   8. The Convergence of Social and Technological Networks

      • Jon Kleinberg

      Pages 29-29

3. Invited Lectures

   1. Principles of Network Computing

      • Yicheng Pan

      Pages 30-39

   2. The Small Community Phenomenon in Networks: Models, Algorithms and Applications

      • Pan Peng

      Pages 40-49

   3. Vertex-Pursuit in Hierarchical Social Networks

      • A. Bonato, D. Mitsche, P. Prałat

      Pages 50-60

   4. A Structural Approach to Prophecy Variables

      • Zipeng Zhang, Xinyu Feng, Ming Fu, Zhong Shao, Yong Li

      Pages 61-71

   5. An Assume/Guarantee Based Compositional Calculus for Hybrid CSP

      • Shuling Wang, Naijun Zhan, Dimitar Guelev

      Pages 72-83

   6. Automatic Verification of Real-Time Systems with Rich Data: An Overview

      • Ernst-Rüdiger Olderog

      Pages 84-93

   7. Program Analysis Using Quantifier-Elimination Heuristics

      • Deepak Kapur

      Pages 94-108

   8. Electron Tomography and Multiscale Biology

      • Albert F. Lawrence, Séastien Phan, Mark Ellisman

      Pages 109-130

4. Contributed Papers

   1. Constant-Time Approximation Algorithms for the Knapsack Problem

      • Hiro Ito, Susumu Kiyoshima, Yuichi Yoshida

      Pages 131-142

   2. Lower Bounds of Shortest Vector Lengths in Random NTRU Lattices

      • Jingguo Bi, Qi Cheng

      Pages 143-155

   3. Polynomial Time Construction of Ellipsoidal Approximations of Zonotopes Given by Generator Descriptions

      • Michal Černý, Miroslav Rada

      Pages 156-163

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 Turing’s 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.

• elliptic curve
• hybrid systems
• key exchange
• multiparty communication
• turing machine
• algorithm analysis and problem complexity

• Department of Computer Science and Engineering, Resource Planning and Generation, Indian Institute of Technology Kanpur, Kanpur, India

  Manindra Agrawal

• Department of Pure Mathematics, Leeds, University of Leeds, UK

  S. Barry Cooper

• Institute of Software, Chinese Academy of Sciences, Beijing, P.R. China

  Angsheng Li

Policies and ethics