|
Program
The conference venue is Hotel Benczúr, 1068 Budapest, Benczúr utca 35.
Click here for maps of the city.
Sunday, August 26
|
15.00 - 18.00 |
Registration
|
Monday, August 27
|
8.00 - 11.00 |
Registration
|
| |
Session chair: Philip Scott
|
|
9.10 - 10.10
|
Ahmed Bouajjani (Invited Talk):
Rewriting Systems with Data - A Framework for Reasoning about Systems with Unbounded Structures over Infinite Data Domains (with
Peter Habermel, Yan Jurski, and Mihaela Sighireanu)
|
|
10.10 - 10.35
|
Henrik Björklund and Thomas Schwentick:
On Notions of Regularity for Data Languages
|
| |
Session chair: Ahmed Bouajjani
|
|
11.00 - 11.25
|
Viviana Bono and Jaroslaw D. M. Kusmierek:
FJMIP: a Calculus for a Modular Object Initialization
|
|
11.25 - 11.50
|
Thomas Colcombet:
Factorisation Forests for Infinite Words - Application to Countable Scattered Linear Orderings
|
|
11.50 - 12.15
|
Michael Hoffmann and Richard M. Thomas:
Notions of Hyperbolicity in Monoids
|
|
12.15 - 12.40
|
Andrea Sattler-Klein:
Some Complexity Results for Prefix Gröbner Bases in Free Monoid Rings
|
| |
Session chair: Richard M. Thomas
|
|
15.00 - 15.25
|
Abdullah N. Arslan:
A Largest Common d-Dimensional Subsequence of Two d-Dimensional Strings
|
|
15.25 - 15.50
|
Didier Caucal and Dinh Trong Hieu:
Path Algorithms on Regular Graphs
|
|
15.50 - 16.15
|
Martin Kutrib and Andreas Malcher:
Real-Time Reversible Iterative Arrays
|
| |
Session chair: Zoltán Ésik
|
|
16.45 - 17.10
|
Miroslav Ciric, Aleksandar Stamenkovic, Jelena Ignjatovic and Tatjana Petkovic:
Factorization of Fuzzy Automata
|
|
17.10 - 17.35
|
Jacques Duparc and Filip Murlak:
On the Topological Complexity of Weakly Recognizable Tree Languages
|
|
17.35 - 18.00
|
Mathias Samuelides and Luc Segoufin:
Complexity of Pebble Tree-Walking Automata
|
|
19.00 - 21.00
|
Welcome Party
in Hotel Benczúr
|
Tuesday, August 28
| |
Session chair: Erzsébet Csuhaj-Varjú
|
|
9.00 - 10.00
|
Oscar H. Ibarra (Invited Talk):
Spiking Neural P Systems: Some Characterizations
(with Sara Woodworth)
|
|
10.00 - 10.25
|
Mihai Ionescu and Dragos Sburlan:
P Systems with Adjoining Controlled Communication Rules
|
| |
Session chair: Oscar H. Ibarra
|
|
10.50 - 11.15
|
Robert Brijder, Miika Langille and Ion Petre:
A String-based Model for Simple Gene Assembly
|
|
11.15 - 11.40
|
Robert Brijder, Hendrik Jan Hoogeboom and Grzegorz Rozenberg:
From Micro to Macro: How the Overlap Graph Determines the Reduction Graph in Ciliates
|
|
11.40 - 12.05
|
Gaëlle Brevier, Romeo Rizzi and Stéphane Vialette:
Pattern Matching in Protein-Protein Interaction Graphs
|
|
12.05 - 12.30
|
Nadia Busi and Claudio Zandron:
On the Computational Power of Genetic Gates with Interleaving Semantics: The Power of Inhibition and Degradation
|
| |
Session chair: Thomas Schwentick
|
|
15.30 - 15.55
|
Clelia De Felice, Gabriele Fici and Rosalba Zizza:
Marked Systems and Circular Splicing
|
|
15.55 - 16.20
|
Michal Kunc:
The Simplest Language Where Equivalence of Finite Substitutions is Undecidable
|
|
16.20 - 16.45
|
Alexander Meduna and Jirí Techet:
Maximal and Minimal Scattered Context Rewriting
|
| |
Session chair: Martin Kutrib
|
|
17.15 - 17.40
|
Alexander Okhotin:
Expressive Power of LL(k) Boolean Grammars
|
|
17.40 - 18.05
|
Henning Bordihn and György Vaszil:
Top-down Deterministic Parsing of Languages Generated by CD Grammar Systems
|
|
18.05 - 18.30
|
Hartmut Messerschmidt and Friedrich Otto:
Strictly Deterministic CD-Systems of Restarting Automata
|
Wednesday, August 29
| |
Session chair: Stephen L. Bloom
|
|
9.00 - 10.00
|
Philip J. Scott (Invited Talk):
Traces, Feedback, and the Geometry of Computation
|
|
10.00 - 10.25
|
Jörg Endrullis, Clemens Grabmayer, Dimitri Hendriks, Ariya Isihara and Jan Willem Klop:
Productivity of Stream Definitions
|
| |
Session chair: Till Tantau
|
|
10.50 - 11.15
|
Eric Bach and Jin-Yi Cai:
A Novel Information Transmission Problem and its Optimal Solution
|
|
11.15 - 11.40
|
Johan Kwisthout:
The Computational Complexity of Monotonicity in Probabilistic Networks
|
|
11.40 - 12.05
|
Puneet Bhateja, Paul Gastin, Madhavan Mukund and K. Narayan Kumar:
Local Testing of Message Sequence Charts is Difficult
|
|
12.05 - 12.30
|
Gábor Erdélyi, Lane A. Hemaspaandra, Jörg Rothe and Holger Spakowski:
On Approximating Optimal Weighted Lobbying, and Frequency of Correctness versus Average-Case Polynomial Time
|
|
12.30 - 12.55
|
Chi-Jen Lu, Shi-Chun Tsai and Hsin-Lung Wu:
Impossibility Results on Weakly Black-Box Hardness Amplification
|
|
15.00 - 18.30
|
Sightseeing Tour,
departure from Hotel Benczúr
|
|
19.00 - 22.00
|
Conference Dinner
on the ship Millenium II, departure from quay 1, Jászai Mari
tér
|
Thursday, August 30
| |
Session chair: Mario Szegedy
|
|
9.00 - 10.00
|
László Lovász (Invited Talk): Approximating Graphs by Graphs and Functions
|
|
10.00 - 10.25
|
Stavros Athanassopoulos, Ioannis Caragiannis, Christos Kaklamanis:
Analysis of Approximation Algorithms for k-Set Cover using Factor-Revealing Linear Programs
|
| |
Session chair: László Lovász
|
|
10.50 - 11.15
|
Leah Epstein, Asaf Levin and Rob van Stee:
Multi-dimensional Packing with Conflicts
|
|
11.15 - 11.40
|
Hadas Shachnai and Omer Yehezkely:
Asymptotic FPTAS for Packing Fragmentable Items with Costs
|
|
11.40 - 12.05
|
Edith Hemaspaandra, Lane A. Hemaspaandra, Till Tantau and Osamu Watanabe:
On the Complexity of Kings
|
|
12.05 - 12.30
|
Michael Fellows, Michael Langston, Frances Rosamond and Peter Shaw:
Efficient Parameterized Preprocessing for Cluster Editing
|
| |
Session chair: Leah Epstein
|
|
15.00 - 15.25
|
Rajat Mittal and Mario Szegedy:
Product Rules in Semidefinite Programming
|
|
15.25 - 15.50
|
Sebastian Dörn and Thomas Thierauf:
The Quantum Query Complexity of Algebraic Properties
|
|
15.50 - 16.15
|
Jin-Yi Cai and Pinyan Lu:
On Block-Wise Symmetric Signatures for Matchgates
|
| |
Session chair: Jin-Yi Cai
|
|
16.45 - 17.10
|
Hans-Georg Breunig:
The Complexity of Membership Problems for Circuits over Sets of Positive Numbers
|
|
17.10 - 17.35
|
Takeyuki Tamura and Tatsuya Akutsu:
An $O(1.787^n)$-time Algorithm for Detecting a Singleton Attractor in a Boolean Network Consisting of AND/OR Nodes
|
|
17.35 - 18.00
|
Gyula Győr:
Representing Boolean OR Function by Quadratic Polynomials Modulo 6
|
|
18.00 - 18.10
|
Invitation to FCT 2009
|
|
