Theory and Applications of Models of Computation 4th International Conference, TAMC 2007, Shanghai, China, May 22-25, 2007, Proceedings

This book constitutes the refereed proceedings of the 4th International Conference on Theory and Applications of Models of Computation, TAMC 2007, held in Shanghai, China in May 2007. The 67 revised full papers presented together with 2 plenary lectures were carefully reviewed and selected from over 500 submissions. All major areas in computer science, mathematics (especially logic) and the physical sciences particularly with regard to computation and computability theory are addressed. The papers ? featuring this crossdisciplinary character ? particularly focus on algorithms, complexity and computability theory, giving the conference a special flavor and distinction.