36. MFCS 2011:
Warsaw,
Poland
Filip Murlak, Piotr Sankowski (Eds.):
Mathematical Foundations of Computer Science 2011 - 36th International Symposium, MFCS 2011, Warsaw, Poland, August 22-26, 2011. Proceedings.
Lecture Notes in Computer Science 6907 Springer 2011, ISBN 978-3-642-22992-3
Invited Papers
Contributed Papers
- Yoram Bachrach:
The Least-Core of Threshold Network Flow Games.
36-47
- Paolo Baldan, Fabio Gadducci, Pawel Sobocinski:
Adhesivity Is Not Enough: Local Church-Rosser Revisited.
48-59
- Sebastian S. Bauer, Uli Fahrenberg, Line Juhl, Kim G. Larsen, Axel Legay, Claus R. Thrane:
Quantitative Refinement for Weighted Modal Transition Systems.
60-71
- Petra Berenbrink, Robert Elsässer, Tom Friedetzky, Lars Nagel, Thomas Sauerwald:
Faster Coupon Collecting via Replication with Applications in Gossiping.
72-83
- Olaf Beyersdorff, Samir Datta, Meena Mahajan, Gido Scharfenberger-Fabian, Karteek Sreenivasaiah, Michael Thomas, Heribert Vollmer:
Verifying Proofs in Constant Depth.
84-95
- Markus Bläser, Radu Curticapean:
The Complexity of the Cover Polynomials for Planar Graphs of Bounded Degree.
96-107
- Michel Blockelet, Sylvain Schmitz:
Model Checking Coverability Graphs of Vector Addition Systems.
108-119
- Andrej Bogdanov, Akinori Kawachi, Hidetoki Tanaka:
Hard Functions for Low-Degree Polynomials over Prime Fields.
120-131
- Benedikt Bollig, Aiswarya Cyriac, Paul Gastin, Marc Zeitoun:
Temporal Logics for Concurrent Recursive Programs: Satisfiability and Model Checking.
132-144
- Rémi Bonnet:
The Reachability Problem for Vector Addition System with One Zero-Test.
145-157
- Christina Boucher:
The Bounded Search Tree Algorithm for the Closest String Problem Has Quadratic Smoothed Complexity.
158-169
- Olivier Bournez, Daniel S. Graça, Amaury Pouly:
Solving Analytic Differential Equations in Polynomial Time over Unbounded Domains.
170-181
- Robert Bredereck, André Nichterlein, Rolf Niedermeier, Geevarghese Philip:
Pattern-Guided Data Anonymization and Clustering.
182-193
- Stanislav Böhm, Stefan Göller:
Language Equivalence of Deterministic Real-Time One-Counter Automata Is NL-Complete.
194-205
- Krishnendu Chatterjee, Laurent Doyen:
Energy and Mean-Payoff Parity Markov Decision Processes.
206-218
- Jacek Chrzaszcz, Aleksy Schubert:
The Role of Polymorphism in the Characterisation of Complexity by Soft Types.
219-230
- David A. Cohen, Páidí Creed, Peter G. Jeavons, Stanislav Zivny:
An Algebraic Theory of Complexity for Valued Constraints: Establishing a Galois Connection.
231-242
- Thomas Colcombet, Clemens Ley, Gabriele Puppis:
On the Use of Guards for Logics with Data.
243-255
- Evgeny Demenkov, Alexander S. Kulikov:
An Elementary Proof of a 3n - o(n) Lower Bound on the Circuit Complexity of Affine Dispersers.
256-265
- Riccardo Dondi, Giancarlo Mauri, Italo Zoppis:
On the Complexity of the l-diversity Problem.
266-277
- Laurent Doyen, Thierry Massart, Mahsa Shirmohammadi:
Infinite Synchronizing Words for Probabilistic Automata.
278-289
- Balder ten Cate, Alessandro Facchini:
Characterizing EF over Infinite Trees and Modal Logic on Transitive Graphs.
290-302
- John Fearnley, Oded Lachish:
Parity Games on Graphs with Medium Tree-Width.
303-314
- Peter Franek, Stefan Ratschan, Piotr Zgliczynski:
Satisfiability of Systems of Equations of Real Analytic Functions Is Quasi-decidable.
315-326
- Pawel Gawrychowski, Artur Jez, Andreas Maletti:
On Minimising Automata with Errors.
327-338
- Petr A. Golovach, Marcin Kaminski, Daniël Paulusma:
Contracting a Chordal Graph to a Split Graph or a Tree.
339-350
- Marats Golovkins, Maksim Kravtsev, Vasilijs Kravcevs:
Quantum Finite Automata and Probabilistic Reversible Automata: R-trivial Idempotent Languages.
351-363
- Edith Hemaspaandra, Henning Schnoor:
A Universally Defined Undecidable Unimodal Logic.
364-375
- Jun Hosoda, Juraj Hromkovic, Taisuke Izumi, Hirotaka Ono, Monika Steinová, Koichi Wada:
On the Approximability of Minimum Topic Connected Overlay and Its Special Instances.
376-387
- Anne-Marie Kermarrec, Christopher Thraves:
Can Everybody Sit Closer to Their Friends Than Their Enemies?
388-399
- Vladimir Kolmogorov:
Submodularity on a Tree: Unifying $L^\natural$ -Convex and Bisubmodular Functions.
400-411
- Andreas Krebs, Nutan Limaye, Srikanth Srinivasan:
Streaming Algorithms for Recognizing Nearly Well-Parenthesized Expressions.
412-423
- Dietrich Kuske, Thomas Weidner:
Size and Computation of Injective Tree Automatic Presentations.
424-435
- Richard J. Lipton, Kenneth W. Regan, Atri Rudra:
Symmetric Functions Capture General Functions.
436-447
- Markus Lohrey:
Compressed Word Problems for Inverse Monoids.
448-459
- Andreas Maletti, Daniel Quernheim:
Pushing for Weighted Tree Automata.
460-471
- Florin Manea, Robert Mercas, Catalin Tiseanu:
Periodicity Algorithms for Partial Words.
472-484
- Alexander Okhotin, Kai Salomaa:
State Complexity of Operations on Input-Driven Pushdown Automata.
485-496
- Christophe Paul, Anthony Perez, Stéphan Thomassé:
Conflict Packing Yields Linear Vertex-Kernels for k -FAST, k -dense RTI and a Related Problem.
497-507
- Kevin Perrot, Eric Rémila:
Transduction on Kadanoff Sand Pile Model Avalanches, Application to Wave Pattern Emergence.
508-519
- Michal Pilipczuk:
Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical Approach.
520-531
- Wladimir Fridman, Bernd Puchala:
Distributed Synthesis for Regular and Contextfree Specifications.
532-543
- Krzysztof Krzywdzinski, Katarzyna Rybarczyk:
Geometric Graphs with Randomly Deleted Edges - Connectivity and Routing Protocols.
544-555
- Ocan Sankur:
Untimed Language Preservation in Timed Systems.
556-567
- Kei Uchizawa, Eiji Takimoto:
Lower Bounds for Linear Decision Trees via an Energy Complexity Argument.
568-579
- Michael Vanden Boom:
Weak Cost Monadic Logic over Infinite Trees.
580-591
- Jianxin Wang, Yongjie Yang, Jiong Guo, Jianer Chen:
Linear Problem Kernels for Planar Graph Problems with Small Distance Property.
592-603
- Mingyu Xiao, Ton Kloks, Sheung-Hung Poon:
New Parameterized Algorithms for the Edge Dominating Set Problem.
604-615
Last update Fri May 25 08:26:28 2012
CET by the DBLP Team —
Data released under the ODC-BY 1.0 license — See also our legal information page