Online proceedings

The online version of the proceedings is now available.

MFCS 2011 Accepted Papers

• Dietrich Kuske and Thomas Weidner. Size and computation of injective tree automatic presentations
• Peter Franek, Stefan Ratschan and Piotr Zgliczynski. Satisfiability of Systems of Equations of Real Analytic Functions is  Quasi-decidable
• Markus Lohrey. Compressed word problems for inverse monoids
• Yoram Bachrach. The Least-Core of Threshold Network Flow Games
• Riccardo Dondi, Giancarlo Mauri and Italo Zoppis. On the Complexity of the l-diversity Problem
• Kévin Perrot and Eric Rémila. Transduction on Kadanoff Sand Pile Model Avalanches, Application to Wave Pattern Emergence.
• Ocan Sankur. Untimed Language Preservation in Timed Systems
• Pawel Gawrychowski, Artur Jeż and Andreas Maletti. On minimising automata with errors
• Evgeny Demenkov and Alexander Kulikov. An Elementary Proof of a 3n-o(n) Lower Bound on the Circuit Complexity of Affine Dispersers
• Olivier Bournez, Daniel Graça and Amaury Pouly. Solving Analytic Differential Equations in Polynomial Time over  Unbounded Domains
• Vladimir Kolmogorov. Submodularity on a tree: Unifying L^♮-convex and bisubmodular functions
• Michal Pilipczuk. Problems parameterized by treewidth tractable in single exponential time: a logical approach
• Christophe Paul, Stéphan Thomassé and Anthony Perez. Conflict Packing yields linear vertex-kernels for Rooted Triplet Inconsistency and related problems
• Alessandro Facchini and Balder Ten Cate. Characterizing EF over Infinite Trees and Modal Logic on Transitive Graphs
• Stanislav Böhm and Stefan Göller. Language equivalence of deterministic real-time one-counter automata is NL-complete
• Olaf Beyersdorff, Samir Datta, Meena Mahajan, Gido Scharfenberger-Fabian, Karteek Sreenivasaiah, Michael Thomas and Heribert Vollmer. Verifying Proofs in Constant Depth
• Krishnendu Chatterjee and Laurent Doyen. Energy and Mean-Payoff Parity Markov Decision Processes
• David A. Cohen, Paidi Creed, Peter G. Jeavons and Stanislav Zivny. An Algebraic Theory of Complexity for Valued Constraints: Establishing a Galois Connection
• Christina Boucher. The Bounded Search Tree Algorithm for the Closest String Problem has Quadratic Smoothed Complexity
• Marats Golovkins, Maksim Kravtsev and Vasilijs Kravcevs. Quantum Finite Automata and Probabilistic Reversible Automata: R-trivial Idempotent Languages
• Jianxin Wang, Yongjie Yang, Jiong Guo and Jianer Chen. Linear Problem Kernels for Planar Graph Problems with Small Distance Property
• Andrej Bogdanov, Akinori Kawachi and Hidetoki Tanaka. Hard Functions for Low-degree Polynomials over Prime Fields
• Mingyu Xiao, Ton Kloks and Sheung-Hung Poon. New Parameterized Algorithms for Edge Dominating Set
• Kei Uchizawa and Eiji Takimoto. Lower Bounds for Linear Decision Trees via An Energy Complexity Argument
• Florin Manea, Robert Mercas and Catalin Tiseanu. Periodicity Algorithms for Partial Words
• Andreas Maletti and Daniel Quernheim. Pushing for weighted tree automata
• Markus Blaeser and Radu Curticapean. The Complexity of the Cover Polynomials for Planar Graphs of Bounded Degree
• Jacek Chrząszcz and Aleksy Schubert. The role of polymorphism in the characterisation of complexity by soft types
• Alexander Okhotin and Kai Salomaa. State complexity of operations on input-driven pushdown automata
• Robert Bredereck, André Nichterlein, Rolf Niedermeier and Geevarghese Philip. Pattern-Guided Data Anonymization and Clustering
• John Fearnley and Oded Lachish. Parity Games On Graphs With Medium Tree-width
• Michael Vanden Boom. Weak Cost Monadic Logic Over Infinite Trees
• Bernd Puchala and Wladimir Fridman. Distributed Synthesis for Regular and Contextfree Specifications
• Jun Hosoda, Juraj Hromkovic, Taisuke Izumi, Hirotaka Ono, Monika Steinová and Koichi Wada. On the Approximability of Minimum Topic Connected Overlay and Its Special Instances
• Andreas Krebs, Nutan Limaye and Srikanth Srinivasan. Streaming algorithms for recognizing nearly well-parenthesized expressions
• Petr Golovach, Marcin Kaminski and Daniel Paulusma. Contracting a chordal graph to a split graph or a tree
• Thomas Colcombet, Clemens Ley and Gabriele Puppis. On the use of guards for logics with data
• Katarzyna Rybarczyk and Krzysztof Krzywdziński. Geometric Graphs with Randomly Deleted Edges - Connectivity and Routing Protocols
• Anne-Marie Kermarrec and Christopher Thraves. Can everybody sit closer to their friends than their enemies?
• Edith Hemaspaandra and Henning Schnoor. A Universally Defined Undecidable Unimodal Logic
• Laurent Doyen, Thierry Massart and Mahsa Shirmohammadi. Infinite Synchronizing Words for Probabilistic Automata
• Paolo Baldan, Fabio Gadducci and Pawel Sobocinski. Adhesivity is not enough: Local Church-Rosser revisited
• Petra Berenbrink, Robert Elsaesser, Tom Friedetzky, Lars Nagel and Thomas Sauerwald. Faster Coupon Collecting via Replication with  Applications in Gossiping
• Michel Blockelet and Sylvain Schmitz. Model Checking Coverability Graphs of Vector Addition Systems
• Richard J. Lipton, Kenneth Regan and Atri Rudra. Symmetric Functions Capture General Functions
• Benedikt Bollig, Aiswarya Cyriac, Paul Gastin and Marc Zeitoun. Temporal Logics for Concurrent Recursive Programs: Satisfiability and Model Checking
• Sebastian Bauer, Uli Fahrenberg, Line Juhl, Kim G Larsen, Axel Legay and Claus Thrane. Quantitative Refinement for Weighted Modal Transition Systems
• Remi Bonnet. The reachability problem for Vector Addition Systems with one zero-test