• 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

Workshop on Non-Classical Models of Automata and Applications (NCMA),
August 31 - September 1

Additional Lectures and Seminars

Monday, building D-1, room 215

 915- 930 Opening
 930-1030 Invited talk: Hendrik J. Hoogeboom, Leiden University, The Netherlands. Automata Walking over Trees
1030-1100 Cofee Break
1100-1200 Session I
= Peter Leupold, Benedek Nagy. 5' -> 3' Watson-Crick Automata with Several Runs
= Peter Cerno, Frantisek Mraz. Clearing Restarting Automata
1200-1400 Lunch
1400-1500 Invited talk: Joachim Niehren, INRIA Lille Nord Europe, France. Streaming Tree Automata and XPath
1500-1530 Session II
= Catalin Ionut Tirnauca. Model Syntax-Directed Translations by Tree Transducers
1530-1600 Cofee Break
1600-1730 Session III
= Bianca Truthe. Target Based Accepting Networks of Evolutionary Processors with Regular Filters
= Tomas Masopust. Regulated Nondeterminism in PDAs: The Non-Regular Case
= Jurgen Dassow, Gema M. Martin, Francisco J. Vico. Evolving under small disruption
1900 Workshopdinner (not covered by the sponsors)

Monday, Wroclaw University, room 119

= 1115-1300 Manuel Bodirsky, Ecole Polytechnique, France, Introduction to Constraint Satisfaction Complexity and Applications in Spatial and Temporal Reasoning

Monday, building C-11, room P01

=1400-1700 Yvonne-Anne Pignolet, ETH Zurich, Game theory and networking
=1700-1800 Stefan Schmid, Universität Paderborn Bad Vibes in Open Airwaves

Tuesday, building D-1, room 215

 930-1030 Invited talk: Klaus Sutner, Carnegie Mellon University, USA. Cellular Automata, Decidability and Phasespace
1030-1100 Cofee Break
1100-1200 Session IV
= Hidenosuke Nishio. Automorphism Classification of Cellular Automata
= Luca Bernardinello, Carlo Ferigato, Lucia Pomello, Stefania Rombola. Closure Operators Associated to Partially Ordered Sets
1200-1400 Lunch
1400-1530 Session V
= Rudolf Freund, Marian Kogler, Sergey Verlan. P Automata with Controlled Use of Minimal Communication Rules
= Maria Paola Bianchi, Beatrice Palano. Events and Languages on Unary Quantum Automata
= Felix Hamza-Lup, Ferucio Laurentiu Tiplea. An Automaton-based Formalism for Cooperative Augmented Reality Systems
1530-1600 Cofee Break
1600-1730 Session VI
= Galina Jiraskova, Pavol Olejar. State Complexity of Union and Intersection of Binary Suffix-Free Languages
= Miklos Bartha. Equivalence relations of Mealy automata
= Viliam Geffert, Carlo Mereghetti, Giovanni Pighizzini. One Pebble versus log(n) Bits

Tuesday, building C-11, room P01

= 900-1100 Yvonne-Anne Pignolet, ETH Zurich, Device Discovery and Delay-Sensitive Aggregation in Wireless Networks
= 1300-1600 Moti Yung, Google Inc. and Columbia University, Security Challenges
= 1600-1700 Stefan Schmid, Universität Paderborn How to design robust networks? Connect to the seniors!

Tuesday, Wroclaw University, room 119

= 1615-1800 Manuel Bodirsky, Ecole Polytechnique, France, On the Scope of the Universal-algebraic Approach to Constraint Satisfaction

17th International Symposium on Fundamentals of Computation Theory (FCT), September 2-4

Additional Lectures and Seminars

Wednesday, building D-20, room 10B

 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

Wednesday, building D-1, room 215

=1100-1230 Yvonne-Anne Pignolet, ETH Zurich, Device Discovery and Delay-Sensitive Aggregation in Wireless Networks

Thursday, building D-20, room 10B

 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

Thursday, building D-1, room 215

=1400-1530 Stephan Waack, Universitat Gottingen. A Generalized Model of PAC Learning and its Applicability

Friday, building D-20, room 10B

 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

International Workshop on DYnamic Networks - Algorithms and Security (DYNAS), September 5

Saturday, building D-1, room 215

 900-1030 Invited talk: Johannes Blomer. Lattice-based Cryptography.
1030-1100 Coffee break
1100-1300 Main Session
= Piotr Borowiecki and Elzbieta Sidorowicz. Dynamic Coloring of Graphs.
= Marta Rybczynska. Evaluating anonymity systems with cover traffic.
= Thomas Locher, David Mysicka, Stefan Schmid, and Roger Wattenhofer. A Peer Activity Study in eDonkey & Kad.
1300-1500 Lunch
 1500-1630 Invited talk: Stefan Dziembowski. Cryptography on Non-Trusted Machines