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

Leslie G. Valiant (auth.), Jianer Chen, S. Barry Cooper (eds.)364202016X, 9783642020162

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.

Table of contents :
Front Matter….Pages –
Neural Computations That Support Long Mixed Sequences of Knowledge Acquisition Tasks….Pages 1-2
Constraints, Graphs, Algebra, Logic, and Complexity….Pages 3-3
Distributed Systems and Their Environments….Pages 4-5
Co-evolution and Information Signals in Biological Sequences….Pages 6-17
The Extended Turing Model as Contextual Tool….Pages 18-28
Strong Positive Reducibilities….Pages 29-38
Fixed-Parameter Algorithms for Graph-Modeled Date Clustering….Pages 39-48
On Spanners of Geometric Graphs….Pages 49-58
Searching Trees: An Essay….Pages 59-70
Approximability and Fixed-Parameter Tractability for the Exemplar Genomic Distance Problems….Pages 71-80
A Quadratic Kernel for 3-Set Packing….Pages 81-87
Quantitative Aspects of Speed-Up and Gap Phenomena….Pages 88-97
Computing the Exact Distribution Function of the Stochastic Longest Path Length in a DAG….Pages 98-107
On the Connection between Interval Size Functions and Path Counting….Pages 108-117
On the Red/Blue Spanning Tree Problem….Pages 118-127
Undecidability of Cost-Bounded Reachability in Priced Probabilistic Timed Automata….Pages 128-137
A Computational Proof of Complexity of Some Restricted Counting Problems….Pages 138-149
Block-Graph Width….Pages 150-157
Minimum Vertex Ranking Spanning Tree Problem on Permutation Graphs….Pages 158-167
On Parameterized Exponential Time Complexity….Pages 168-177
Best-Order Streaming Model….Pages 178-191
Behavioral and Logical Equivalence of Stochastic Kripke Models in General Measurable Spaces….Pages 192-200
Influence of Tree Topology Restrictions on the Complexity of Haplotyping with Missing Data….Pages 201-210
Improved Deterministic Algorithms for Weighted Matching and Packing Problems….Pages 211-220
Parameterized Complexity of Coloring Problems: Treewidth versus Vertex Cover….Pages 221-230
Discovering Almost Any Hidden Motif from Multiple Sequences in Polynomial Time with Low Sample Complexity and High Success Probability….Pages 231-240
A Complete Characterisation of the Linear Clique-Width of Path Powers….Pages 241-250
Preserving Privacy versus Data Retention….Pages 251-260
Kolmogorov Complexity and Combinatorial Methods in Communication Complexity….Pages 261-270
An Almost Totally Universal Tile Set….Pages 271-280
Linear Kernel for Planar Connected Dominating Set….Pages 281-290
A Simple Greedy Algorithm for the k -Disjoint Flow Problem….Pages 291-300
Minimizing AND-EXOR Expressions for Multiple-Valued Two-Input Logic Functions….Pages 301-310
Exact and Experimental Algorithms for a Huffman-Based Error Detecting Code….Pages 311-324
Terminal Coalgebras for Measure-Polynomial Functors….Pages 325-334
High Minimal Pairs in the Enumeration Degrees….Pages 335-344
Searching a Circular Corridor with Two Flashlights….Pages 345-359
On the Complexity of the Multiple Stack TSP, k STSP….Pages 360-369
Linear Programming Based Approximation Algorithms for Feedback Set Problems in Bipartite Tournaments….Pages 370-379
An Online Algorithm for Applying Reinforcement Learning to Handle Ambiguity in Spoken Dialogues….Pages 380-389
A Fixed-Parameter Enumeration Algorithm for the Weighted FVS Problem….Pages 390-399
On the Tractability of Maximal Strip Recovery….Pages 400-409
Greedy Local Search and Vertex Cover in Sparse Random Graphs….Pages 410-419
Embedding the Diamond Lattice in the c.e. tt -Degrees with Superhigh Atoms….Pages 420-429
Feasibility of Motion Planning on Directed Graphs….Pages 430-439
Polynomial-Time Algorithm for Sorting by Generalized Translocations….Pages 440-449
The Two-Guard Polygon Walk Problem….Pages 450-459
Approximation and Hardness Results for Label Cut and Related Problems….Pages 460-469
An Observation on Non-Malleable Witness-Indistinguishability and Non-Malleable Zero-Knowledge….Pages 470-479
Back Matter….Pages –