Theory and Applications of Models of Computation: 5th International Conference, TAMC 2008, Xi'an, China, April 25-29, 2008, Proceedings (Lecture Notes in Computer Science, 4978)

Annotation This book constitutes the refereed proceedings of the 5th International Conference on Theory and Applications of Models of Computation, TAMC 2008, held in Xi'an, China in April 2008. The 48 revised full papers presented together with 2 invited talks and 1 plenary lecture were carefully reviewed and selected from 192 submissions. The papers address current issues of all major areas in computer science, mathematics (especially logic) and the physical sciences - computation, algorithms, complexity and computability theory in particular. With this crossdisciplinary character the conference is given a special flavor and distinction Front Matter....Pages - Differential Privacy: A Survey of Results....Pages 1-19 On the Complexity of Measurement in Classical Physics....Pages 20-30 Quantum Walk Based Search Algorithms....Pages 31-46 Propositional Projection Temporal Logic, B $\ddot{u}$ chi Automata and ω -Regular Expressions....Pages 47-58 Genome Rearrangement Algorithms for Unsigned Permutations with O (log n ) Singletons....Pages 59-69 On the Complexity of the Hidden Subgroup Problem....Pages 70-81 An O * (3.52 3k ) Parameterized Algorithm for 3-Set Packing....Pages 82-93 Indistinguishability and First-Order Logic....Pages 94-104 Derandomizing Graph Tests for Homomorphism....Pages 105-115 Definable Filters in the Structure of Bounded Turing Reductions....Pages 116-124 Distance Constrained Labelings of Trees....Pages 125-135 A Characterization of NC k by First Order Functional Programs....Pages 136-147 The Structure of Detour Degrees....Pages 148-159 Hamiltonicity of Matching Composition Networks with Conditional Edge Faults....Pages 160-169 Local 7-Coloring for Planar Subgraphs of Unit Disk Graphs....Pages 170-181 Generalized Domination in Degenerate Graphs: A Complete Dichotomy of Computational Complexity....Pages 182-191 More on Weak Bisimilarity of Normed Basic Parallel Processes....Pages 192-203 Extensions of Embeddings in the Computably Enumerable Degrees....Pages 204-211 An Improved Parameterized Algorithm for a Generalized Matching Problem....Pages 212-222 Deterministic Hot-Potato Permutation Routing on the Mesh and the Torus....Pages 223-233 Efficient Algorithms for Model-Based Motif Discovery from Multiple Sequences....Pages 234-245 Ratio Based Stable In-Place Merging....Pages 246-257 A Characterisation of the Relations Definable in Presburger Arithmetic....Pages 258-269 Finding Minimum 3-Way Cuts in Hypergraphs....Pages 270-281 Inapproximability of Maximum Weighted Edge Biclique and Its Applications....Pages 282-293 Symbolic Algorithm Analysis of Rectangular Hybrid Systems....Pages 294-305 On the OBDD Complexity of the Most Significant Bit of Integer Multiplication....Pages 306-317 Logical Closure Properties of Propositional Proof Systems....Pages 318-329 Graphs of Linear Clique-Width at Most 3....Pages 330-341 A Well-Mixed Function with Circuit Complexity 5 n ± o ( n ): Tightness of the Lachish-Raz-Type Bounds....Pages 342-350 A Logic for Distributed Higher Order π -Calculus....Pages 351-363 Minimum Maximal Matching Is NP-Hard in Regular Bipartite Graphs....Pages 364-374 A Topological Study of Tilings....Pages 375-387 A Denotational Semantics for Total Correctness of Sequential Exact Real Programs....Pages 388-399 Weak Bisimulations for the Giry Monad (Extended Abstract)....Pages 400-409 Approximating Border Length for DNA Microarray Synthesis....Pages 410-422 On a Question of Frank Stephan....Pages 423-432 A Practical Parameterized Algorithm for the Individual Haplotyping Problem MLF....Pages 433-444 Improved Algorithms for Bicluster Editing....Pages 445-456 Generation Complexity Versus Distinction Complexity....Pages 457-466 Balancing Traffic Load Using One-Turn Rectilinear Routing....Pages 467-478 A Moderately Exponential Time Algorithm for Full Degree Spanning Tree....Pages 479-489 Speeding up Dynamic Programming for Some NP-Hard Graph Recoloring Problems....Pages 490-501 A Linear-Time Algorithm for Finding All Door Locations That Make a Room Searchable....Pages 502-513 Model Theoretic Complexity of Automatic Structures (Extended Abstract)....Pages 514-525 A Separation between Divergence and Holevo Information for Ensembles....Pages 526-541 Unary Automatic Graphs: An Algorithmic Perspective....Pages 542-553 Search Space Reductions for Nearest-Neighbor Queries....Pages 554-567 Total Degrees and Nonsplitting Properties of $\Sigma_2^0$ Enumeration Degrees....Pages 568-578 s-Degrees within e-Degrees....Pages 579-587 The Non-isolating Degrees Are Upwards Dense in the Computably Enumerable Degrees....Pages 588-596 Back Matter....Pages - This Proceedings Volume Examines All Major Areas In Computer Science, Mathematics (especially Logic) And The Physical Sciences, Especially Computation, Algorithms, Complexity And Computability Theory.