Theory and Applications of Models of Computation : 6th Annual Conference, TAMC 2009, Changsha, China, May 18-22, 2009. Proceedings

Theory and Applications of Models of Computation (TAMC) is an inter- tional conference series with an interdisciplinary character, bringing together researchers working in computer science, mathematics (especially logic) and the physical sciences. This crossdisciplinary character, together with its focus on - gorithms, complexity and computability theory, gives the conference a special ?avor and distinction. TAMC2009wasthesixthconferenceintheseries.Theprevious?vemeetings wereheldduringMay17-19,2004inBeijing,May17-20,2005inKunming,May 15-20, 2006 in Beijing, May 22-25, 2007 in Shanghai, and April 25-29, 2008 in Xi'an. TAMC 2009 was held in ChangSha, during May 18-22, 2009. Next year will see a new departure, namely, the ?rst TAMC conference to be held outside of Asia. TAMC 2010 will be held in Prague, capital of the Czech Republic. At TAMC 2009 we had three plenary speakers, Leslie Valiant (Harvard U- versity, USA), Moshe Vardi (Rice University, USA) and Matthew Hennessy (Trinity College, Ireland), giving one-hour talks each. Professor Valiant spoke on "Neural Computations That Support Long Mixed Sequence of Knowledge Acquisition Tasks," Professor Vardi on "Constraints, Graphs, Algebra, Logic, and Complexity," and Professor Hennessy on "Distributed Systems and Their Environments." Their respective abstracts accompanying the talks are included in these proceedings.