16th International Symposium on Fundamentals of
Computation Theory
August 27-30, 2007, Budapest, Hungary

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

9.00 - 9.10 Opening

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

10.35 - 11.00 Break

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

12.40 - 15.00 Lunch

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

16.15 - 16.45 Break

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

10.25 - 10.50 Break

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

12.30 - 15.30 Lunch

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

16.45 - 17.15 Break

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

10.25 - 10.50 Break

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

12.55 - 15.00 Lunch

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

10.25 - 10.50 Break

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

12.30 - 15.00 Lunch

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

16.15 - 16.45 Break

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

18.10 - 18.20 Closing