دانلود کتاب 5699: Fundamentals of Computation Theory: 17th International Symposium, FCT 2009, Wroclaw, Poland, September 2-4, 2009, Proceedings

فهرست مطالب :

Front Matter....Pages -
How to Guard the Guards Themselves....Pages 1-2
Alternating Weighted Automata....Pages 3-13
Maintaining Arrays of Contiguous Objects....Pages 14-25
The k -Anonymity Problem Is Hard....Pages 26-37
Independence Results for n -Ary Recursion Theorems....Pages 38-49
Depletable Channels: Dynamics and Behaviour....Pages 50-61
Noise-Resilient Group Testing: Limitations and Constructions....Pages 62-73
Martingales on Trees and the Empire Chromatic Number of Random Trees....Pages 74-83
Competitive Group Testing and Learning Hidden Vertex Covers with Minimum Adaptivity....Pages 84-95
Combinatorial Queries and Updates on Partial Words....Pages 96-108
The Longest Haplotype Reconstruction Problem Revisited....Pages 109-120
Earliest Query Answering for Deterministic Nested Word Automata....Pages 121-132
Multiway In-Place Merging....Pages 133-144
On Convex Greedy Embedding Conjecture for 3-Connected Planar Graphs....Pages 145-156
On Random Betweenness Constraints....Pages 157-168
Directed Graphs of Entanglement Two....Pages 169-180
Parametrized Regular Infinite Games and Higher-Order Pushdown Strategies....Pages 181-192
Computing Role Assignments of Chordal Graphs....Pages 193-204
Three-Valued Abstractions of Markov Chains: Completeness for a Sizeable Fragment of PCTL....Pages 205-216
Closure Operators for Order Structures....Pages 217-229
Correcting Sorted Sequences in a Single Hop Radio Network....Pages 230-241
A Local Distributed Algorithm to Approximate MST in Unit Disc Graphs....Pages 242-249
Small-Space Analogues of Valiant’s Classes....Pages 250-261
Small Weakly Universal Turing Machines....Pages 262-273
Open Maps Bisimulations for Higher Dimensional Automata Models....Pages 274-286
Decision Version of the Road Coloring Problem Is NP-Complete....Pages 287-297
NP-Completeness of st -Orientations for Plane Graphs....Pages 298-309
Equivalence of Deterministic Nested Word to Word Transducers....Pages 310-322
Reachability in K 3,3 -Free Graphs and K 5 -Free Graphs Is in Unambiguous Log-Space....Pages 323-334
Energy Complexity and Depth of Threshold Circuits....Pages 335-345
1-Local 17/12-Competitive Algorithm for Multicoloring Hexagonal Graphs....Pages 346-356
Back Matter....Pages -