Theory and Applications of Models of Computation

1. Front Matter

   PDF

2. Plenary Talks

   1. Neural Computations That Support Long Mixed Sequences of Knowledge Acquisition Tasks

      • Leslie G. Valiant

      Pages 1-2

   2. Constraints, Graphs, Algebra, Logic, and Complexity

      • Moshe Y. Vardi

      Pages 3-3

   3. Distributed Systems and Their Environments

      • Matthew Hennessy

      Pages 4-5

3. Invited Special Session: Models of Computation

   1. Co-evolution and Information Signals in Biological Sequences

      • Alessandra Carbone, Linda Dib

      Pages 6-17

   2. The Extended Turing Model as Contextual Tool

      • S. Barry Cooper

      Pages 18-28

   3. Strong Positive Reducibilities

      • Andrea Sorbi

      Pages 29-38

4. Invited Special Session: Algorithms and Complexity

   1. Fixed-Parameter Algorithms for Graph-Modeled Date Clustering

      • Jiong Guo

      Pages 39-48

   2. On Spanners of Geometric Graphs

      • Iyad A. Kanj

      Pages 49-58

   3. Searching Trees: An Essay

      • Henning Fernau, Daniel Raible

      Pages 59-70

   4. Approximability and Fixed-Parameter Tractability for the Exemplar Genomic Distance Problems

      • Binhai Zhu

      Pages 71-80

5. Contributed Papers

   1. A Quadratic Kernel for 3-Set Packing

      • Faisal N. Abu-Khzam

      Pages 81-87

   2. Quantitative Aspects of Speed-Up and Gap Phenomena

      • Klaus Ambos-Spies, Thorsten Kräling

      Pages 88-97

   3. Computing the Exact Distribution Function of the Stochastic Longest Path Length in a DAG

      • Ei Ando, Hirotaka Ono, Kunihiko Sadakane, Masafumi Yamashita

      Pages 98-107

   4. On the Connection between Interval Size Functions and Path Counting

      • Evangelos Bampas, Andreas-Nikolas Göbel, Aris Pagourtzis, Aris Tentes

      Pages 108-117

   5. On the Red/Blue Spanning Tree Problem

      • Sergey Bereg, Minghui Jiang, Boting Yang, Binhai Zhu

      Pages 118-127

   6. Undecidability of Cost-Bounded Reachability in Priced Probabilistic Timed Automata

      • Jasper Berendsen, Taolue Chen, David N. Jansen

      Pages 128-137

   7. A Computational Proof of Complexity of Some Restricted Counting Problems

      • Jin-Yi Cai, Pinyan Lu, Mingji Xia

      Pages 138-149

   8. Block-Graph Width

      • Maw-Shang Chang, Ling-Ju Hung, Ton Kloks, Sheng-Lung Peng

      Pages 150-157

   9. Minimum Vertex Ranking Spanning Tree Problem on Permutation Graphs

      • Ruei-Yuan Chang, Guanling Lee, Sheng-Lung Peng

      Pages 158-167

This book constitutes the refereed proceedings of the 6th International Conference on Theory and Applications of Models of Computation, TAMC 2009, held in Changsha, China in May 2009. The 39 full papers presented together with 7 invited papers as well as 3 plenary talks were selected from 86 submissions. The papers address the three main themes of the conference which were Computability, Complexity, and Algorithms. The conference aimed to bring together researchers with interests in theoretical computer science, algorithmic mathematics, and applications to the physical sciences.

• algebra
• algorithm
• algorithms
• automata
• complexity
• computability
• computer science
• constraints
• distributed systems
• exponential time
• logic
• models of computation
• path counting
• tree topology
• undecidability
• algorithm analysis and problem complexity

• Department of Computer Science and Engineering, Texas A&M University, Texas, USA

  Jianer Chen

• School of Mathematics, University of Leeds, U.K.

  S. Barry Cooper

Policies and ethics