• home
  • general information
  • call for papers
  • invited speakers
  • committees
  • sponsors
  • program
  • workshops
  • lectures
  • [joint programs]
  • Proceedings LNCS 5699
  • History of FCTs

FCT 2009
17th International Symposium on
Fundamentals of Computation Theory

September 2-4, 2009, Wrocław, Poland

Conference program

Wednesday

 900-1030 Invited talk: Moti Yung. How to Guard the Guards Themselves
1030-1100 Coffee break
1100-1240 Session I
= Paola Bonizzoni, Gianluca Della Vedova, Riccardo Dondi. The k-anonymity Problem is Hard
= Fabian Wagner, Thomas Thierauf. Reachability in K_{3,3}-free Graphs and K_5-free Graphs is in Unambiguous Log-Space
= Pim van 't Hof, Daniel Paulusma, Johan Van Rooij. Computing role assignments of chordal graphs
= Florin Manea, Adrian Diaconu, Catalin Tiseanu. Combinatorial Queries and Updates on Partial Words
1240-1430 Lunch
1430-1610 Session II
= Kei Uchizawa, Takao Nishizeki, Eiji Takimoto. Energy Complexity and Depth of Threshold Circuits
= Meena Mahajan, Raghavendra Rao B V. Small-space analogues of Valiant's classes
= Michael Bender, Sandor Fekete, Tom Kamphans, Nils Schweer. Maintaining Arrays of Contiguous Objects
= Viliam Geffert, Jozef Gajdoš. Multiway In-Place Merging
1610-1640 Coffee break
1640-1820 Session III
= Mahdi Cheraghchi. Noise-Resilient Group Testing: Limitations and Constructions
= Andreas Goerdt. On random betweenness constraints
= Michael Huth, Nir Piterman, Daniel Wagner. Three-Valued Abstractions of Markov Chains: Completeness for a Sizeable Fragment of PCTL
= Peter Damaschke, Azam Sheikh Muhammad. Competitive Group Testing and Learning Hidden Vertex Covers with Minimum Adaptivity

Thursday

 900-1030 Invited talk: Martin Dietzfelbinger. In Memoriam Prof. Dr. math. Ingo Wegener
1030-1100 Coffee break
1100-1310 Session IV
= Ryszard Janicki, Dai Tri Man Le, Nadezhda Zubkova. Closure Operators for Order Structures
= Elena Oshevskaya. Open Maps Bisimulations for Higher Dimensional Automata Models
= Pietro Cenciarelli, Daniele Gorla, Ivano Salvo. Depletable Channels: Dynamics and Behaviour
= Turlough Neary, Damien Woods. Small weakly universal Turing machines
= John Case, Samuel Moelius. Independence Results for n-ary Recursion Theorems
1310-1400 Lunch
1530-1830 Conference trip
1900 Gala dinner - Karczma Lwowska

Friday

 900-1030 Invited talk: Thomas A. Henzinger. Alternating Weighted Automata
1030-1100 Coffee break
1100-1240 Session V
= Erich Graedel, Lukasz Kaiser, Roman Rabinovich. Directed Graphs of Entanglement Two
= Olivier Gauwin, Joachim Niehren, Sophie Tison. Earliest Query Answering for Deterministic Nested Word Automata
= Slawomir Staworko, Gregoire Laurence, Aurélien Lemay, Joachim Niehren. Equivalence of Deterministic Nested Word to Word Transducers
= Paul Hänsch, Michaela Slaats, Wolfgang Thomas. Parametrized Regular Infinite Games and Higher-Order Pushdown Strategies
1240-1430 Lunch
1430-1610 Session VI
= Colin Cooper, Andrew McGrae, Michele Zito. Martingales on Trees and the Empire Chromatic Number of Random Trees
= Rafal Witkowski. 1-local 17/12-competitive Algorithm for Multicoloring Hexagonal Graphs
= Adam Roman. Decision Version of the Road Coloring Problem is NP-complete
= Sadish Sadasivam, Huaming Zhang. NP-Completeness of st-orientations for plane graphs
1610-1640 Coffee break
1640-1820 Session VII
= Subhas Ghosh, Koushik Sinha. On Convex Greedy Embedding Conjecture for 3-Connected Planar Graphs
= Krzysztof Krzywdziński. A Local Distributed Algorithm to Approximate MST in Unit Disc Graphs
= Riccardo Dondi. The Longest Haplotype Reconstruction Problem Revisited
= Marcin Kik. Correcting Sorted Sequences in a Single Hop Radio Network