17. FCT 2009: Wroclaw, Poland

Invited Lectures

• Moti Yung:
  How to Guard the Guards Themselves. 1-2
  
• Krishnendu Chatterjee, Laurent Doyen, Thomas A. Henzinger:
  Alternating Weighted Automata. 3-13
  

Contributions

• Michael A. Bender, Sándor P. Fekete, Tom Kamphans, Nils Schweer:
  Maintaining Arrays of Contiguous Objects. 14-25
  
• Paola Bonizzoni, Gianluca Della Vedova, Riccardo Dondi:
  The k-Anonymity Problem Is Hard. 26-37
  
• John Case, Samuel E. Moelius:
  Independence Results for n-Ary Recursion Theorems. 38-49
  
• Pietro Cenciarelli, Daniele Gorla, Ivano Salvo:
  Depletable Channels: Dynamics and Behaviour. 50-61
  
• Mahdi Cheraghchi:
  Noise-Resilient Group Testing: Limitations and Constructions. 62-73
  
• Colin Cooper, Andrew R. A. McGrae, Michele Zito:
  Martingales on Trees and the Empire Chromatic Number of Random Trees. 74-83
  
• Peter Damaschke, Azam Sheikh Muhammad:
  Competitive Group Testing and Learning Hidden Vertex Covers with Minimum Adaptivity. 84-95
  
• Adrian Diaconu, Florin Manea, Catalin Tiseanu:
  Combinatorial Queries and Updates on Partial Words. 96-108
  
• Riccardo Dondi:
  The Longest Haplotype Reconstruction Problem Revisited. 109-120
  
• Olivier Gauwin, Joachim Niehren, Sophie Tison:
  Earliest Query Answering for Deterministic Nested Word Automata. 121-132
  
• Viliam Geffert, Jozef Gajdos:
  Multiway In-Place Merging. 133-144
  
• Subhas Kumar Ghosh, Koushik Sinha:
  On Convex Greedy Embedding Conjecture for 3-Connected Planar Graphs. 145-156
  
• Andreas Goerdt:
  On Random Betweenness Constraints. 157-168
  
• Erich Grädel, Lukasz Kaiser, Roman Rabinovich:
  Directed Graphs of Entanglement Two. 169-180
  
• Paul Hänsch, Michaela Slaats, Wolfgang Thomas:
  Parametrized Regular Infinite Games and Higher-Order Pushdown Strategies. 181-192
  
• Pim van 't Hof, Daniël Paulusma, Johan M. M. van Rooij:
  Computing Role Assignments of Chordal Graphs. 193-204
  
• Michael Huth, Nir Piterman, Daniel Wagner:
  Three-Valued Abstractions of Markov Chains: Completeness for a Sizeable Fragment of PCTL. 205-216
  
• Ryszard Janicki, Dai Tri Man Le, Nadezhda Zubkova:
  Closure Operators for Order Structures. 217-229
  
• Marcin Kik:
  Correcting Sorted Sequences in a Single Hop Radio Network. 230-241
  
• Krzysztof Krzywdzinski:
  A Local Distributed Algorithm to Approximate MST in Unit Disc Graphs. 242-249
  
• Meena Mahajan, B. V. Raghavendra Rao:
  Small-Space Analogues of Valiant's Classes. 250-261
  
• Turlough Neary, Damien Woods:
  Small Weakly Universal Turing Machines. 262-273
  
• Elena S. Oshevskaya:
  Open Maps Bisimulations for Higher Dimensional Automata Models. 274-286
  
• Adam Roman:
  Decision Version of the Road Coloring Problem Is NP-Complete. 287-297
  
• Sadish Sadasivam, Huaming Zhang:
  NP-Completeness of st-Orientations for Plane Graphs. 298-309
  
• Slawomir Staworko, Grégoire Laurence, Aurélien Lemay, Joachim Niehren:
  Equivalence of Deterministic Nested Word to Word Transducers. 310-322
  
• Thomas Thierauf, Fabian Wagner:
  Reachability in K_{3, 3}-Free Graphs and K₅-Free Graphs Is in Unambiguous Log-Space. 323-334
  
• Kei Uchizawa, Takao Nishizeki, Eiji Takimoto:
  Energy Complexity and Depth of Threshold Circuits. 335-345
  
• Rafal Witkowski:
  1-Local 17/12-Competitive Algorithm for Multicoloring Hexagonal Graphs. 346-356