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

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 -