MFCS 2009
34th International Symposium on
Mathematical Foundations of Computer Science
August 24 - 28, 2009


Monday August 24, 2009

9:00 - 10:00 Albert Atserias: Four subareas of the theory of constraints, and their links (invited talk)

10:00 - 10:30 coffee break

10:30 - 12:00 Session A

Ezra Resnick, Yoram Bachrach, Reshef Meir and Jeffrey Rosenschein: The Cost of Stability in Network Flow Games

Stavros Athanassopoulos, Ioannis Caragiannis, Christos Kaklamanis and Evi Papaioannou: Energy-efficient communication in multi-interface wireless networks

Vincenzo Auletta, Paolo Penna and Giuseppe Persiano: Private capacities in mechanism design

10:30 - 12:00 Session B

Diego Figueira and Luc Segoufin: Future-looking logics on data words and trees

Tony Tan: On Pebble Automata for Data Languages with Decidable Emptiness Problem

Lukasz Kaiser: Synthesis for Structure Rewriting Systems

12:00 - 15:00 lunch

15:00 - 17:00 Session A

Stavros Athanassopoulos, Ioannis Caragiannis, Christos Kaklamanis and Maria Kyropoulou: An improved approximation bound for spanning star forest and color saving

Johannes Köbler and Sebastian Kuhnert: The k-tree isomorphism problem is complete for logspace

Ivona Bezakova and William A. Rummler: Sampling and Counting Edge Covers in 3-Regular Graphs

Kyriaki Ioannidou, George Mertzios and Stavros Nikolopoulos: The Longest Path Problem is Polynomial on Interval Graphs

15:00 - 17:00 Session B

Manfred Kufleitner and Pascal Weil: On FO2 quantifier alternation over words

Wouter Gelade, Marc Gyssens and Wim Martens: Regular expressions with Counting: Weak versus Strong Determinism

Arturo Carpi and Flavio D'Alessandro: The synchronization problem for locally strongly transitive automata

Pawel Gawrychowski and Artur Jez: Hyper-minimising and k-hyper-minimising the automaton in O (|δ| log n)

Tuesday August 25, 2009

9:30 - 10:30 Peter Widmayer: How to Sort a Train (invited talk)

10:30 - 11:00 coffee break

11:00 - 12:30 Session A

Anuj Dawar and Yuguo He: Parameterized Complexity Classes under Logical Reductions

Yi Cao, Joseph Culberson and Lorna Stewart: DP-complete Problems Derived from Extremal NP-complete Properties

Sagarmoy Dutta and Piyush P Kurur: Representing groups on graphs

11:00 - 12:30 Session B

Ahmet Kara, Volker Weber, Martin Lange and Thomas Schwentick: On the Hybrid Extension of CTL and CTL+

Arne Meier, Martin Mundhenk, Thomas Schneider, Michael Thomas, Volker Weber and Felix Weiss: The Complexity of Satisfiability for Fragments of Hybrid Logic - Part I

Stanislav Zivny, David A. Cohen and Peter G. Jeavons: The Expressive Power of Binary Submodular Functions

12:30 - 15:00 lunch

15:00 - 16:00 Didier Caucal: Synchronization of regular automata (invited talk)

16:00 - 16:30 coffee break

16:30 - 18:00 Session A

Daniel Kirsten: An Algebraic Characterization of Semirings for which the Support of a Recognizable Series is Always Recognizable

Tomi Kärki, Anne Lacroix and Michel Rigo: On the recognizability of self-generating sets

Francisco Claude and Gonzalo Navarro: Indexing Straight-Line Programs

16:30 - 18:00: Session B

Bakhadyr Khoussainov, Jiamou Liu and Imran Khaliq: A Dynamic Algorithm for Reachability Games Played on Trees

Sven Schewe: From Parity and Payoff Games to Linear Programming

Marco Faella: Admissible Strategies in Infinite Games over Graphs

Wednesday August 26, 2009

9:30 - 10:30 Muthu Muthukrishnan: Stochastic Data Streams (invited talk)

10:30 - 11:00 coffee break

11:00 - 12:30 Session A

Mathieu Chapelle, Frédéric Mazoit and Ioan Todinca: Constructing Brambles

Petr Golovach and Pinar Heggernes: Choosability of P5-free graphs

Alessandro Bianco, Marco Faella, Fabio Mogavero and Aniello Murano: Balanced Paths in Colored Graphs

11:00 - 12:30 Session B

Giulio Manzonetto: A general class of models of H*

Marco Gaboardi, Luca Roversi and Luca Vercelli: Multiplicative Exponential Linear Logic can be levelled

Delia Kesner and Fabien Renaud: The prismoid of resources

12:30 - 15:00 lunch

Thursday August 27, 2009

9:30 - 10:30 Pavlos Spirakis: Recent Advances in Population Protocols (invited talk)

10:30 - 11:00 coffee break

11:00 - 12:30 Session A

Periklis Papakonstantinou: On the Structure of Optimal Greedy Computation (for Job Scheduling)

Kai Plociennik: A Probabilistic PTAS for Shortest Common Superstring

Feodor Dragan and Yang Xiang: How to use spanning trees to navigate in graphs

11:00 - 12:30 Session B

Rupert Hölzl, Thorsten Kräling and Wolfgang Merkle: Time-bounded Kolmogorov complexity and Solovay functions

Xizhong Zheng and Robert Rettinger: Points on Computable Curves of Computable Lengths

Tadao Takaoka: Partial Solution and Entropy

12:30 - 15:00 lunch

15:00 - 16:00 Javier Esparza: Stochastic process creation (invited talk)

16:00 - 16:30 coffee break

16:30 - 18:00 Session A

Gaétan Richard:(Un)decidability of injectivity and surjectivity in one-dimensional sand automaton

Jarkko Kari, Pascal Vanier and Thomas Zeume: Bounds on non-surjective cellular automata

Violetta Lonati and Matteo Pradella: Snake-Deterministic Tiling Systems

16:30 - 18:00 Session B

Irénée Briquel and Pascal Koiran: A Dichotomy Theorem for Polynomial Evaluation

Martin Roetteler: Quantum algorithms for hidden shift problems: quadratics and functions of large Gowers norm

Kohtaro Tadaki: Partial Randomness and Dimension of Recursively Enumerable Reals

Friday August 28, 2009

9:30 - 10:30 Krishnendu Chatterjee, Thomas A. Henzinger and Florian Horn: Stochastic Games with Finitary Objectives (invited talk)

10:30 - 11:00 coffee break

11:00 - 12:30 Session A

Sotiris Nikoletseas, Christoforos Raptopoulos and Paul Spirakis: Colouring Non-Sparse Random Intersection Graphs

Adrian Kosowski and Alfredo Navarra: Graph Decomposition for Improving Memoryless Periodic Exploration

Michael Fellows, Jiong Guo, Hannes Moser and Rolf Niedermeier: A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems

11:00 - 12:30 Session B

Bernd Borchert, Pierre McKenzie and Klaus Reinhardt: Few Product Gates but Many Zeros

Kei Uchizawa, Eiji Takimoto and Takao Nishizeki: Size and Energy of Threshold Circuits Computing Mod Functions

Vikraman Arvind and Pushkar Joglekar: Arithmetic Circuits, Monomial Algebras and Finite Automata

12:30 - 15:00 lunch

15:00 - 16:30 Session A

Julien Degorre, Marc Kaplan, Sophie Laplante and Jérémie Roland: The communication complexity of non-signaling distributions

Nadja Betzler and Britta Dorn: Towards a Dichotomy of Finding Possible Winners in Elections Based on Scoring Rules

Paolo D'Arco, Alfredo De Santis, Anna Lisa Ferrara and Barbara Masucci: Security and Tradeoffs of the Akl-Taylor Scheme and its Variants

15:00 - 16:30 Session B

Mark Braverman, Stephen Cook, Pierre McKenzie, Rahul Santhanam and Dustin Wehr: Branching Programs for Tree Evaluation

Alexander Kartzow: FO Model Checking on Nested Pushdown Trees

P. Madhusudan and Mahesh Viswanathan: Query Automata for Nested Words

Social events: